[알고리즘] 플로이드 - 백준 11403 1389 11404 2458 1956 14938

모든 순간의 다익 + dp로 생각하면 될듯

 

11403 경로 찾기

import sys
 
input = sys.stdin.readline
 
N = int(input())
 
graph = []
 
for _ in range(N):
    graph.append(list(map(int, input().split())))
    
for i in range(N):
    for j in range(N):
        for k in range(N):
            if graph[j][k] == 1 or (graph[j][i] == 1 and graph[i][k] == 1):
                graph[j][k] = 1
                
for x in graph:
    for y in x:
        print(y, end = " ")
    print("")

 

1389 케빈 베이컨의 6단계 법칙

import sys
input = sys.stdin.readline
INF = int(1e9)
N, M = map(int, input().split())
graph = [[INF]*(N+1) for _ in range(N+1)] 
#lev = [6] * (N+1)
 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
 
for i in range(1, N+1):
    for j in range(1, N+1):
        if i == j:
            graph[i][j] = 0
 
     
for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
            
 
 
ans = 0
 
for i in range(N, 0, -1):
    s = sum(graph[i][1:])
    if INF >= s:
        INF = s
        ans = i
        
print(ans)

 

11404 플로이드

import sys
import heapq
input = sys.stdin.readline
 
INF = int(1e9)
 
N = int(input())
M = int(input())
 
cost = [[INF]*(N) for _ in range(N)]
 
for _ in range(M):
    a, b, c = map(int, input().split())
    if cost[a-1][b-1] > c:
        cost[a-1][b-1] = c
 
for i in range(N):
    for j in range(N):
        for k in range(N):
            if j != k and cost[j][k] > cost[j][i] +cost[i][k]:
                cost[j][k] = cost[j][i] + cost[i][k]
                
 
for x in cost:
    for c in x:
        if c == INF:
            print(0, end = ' ')
        else:
            print(c, end = ' ')
            
    print("")

 

2458 키 순서

 

import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
 
graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
 
for _ in range(M):
    u, d = map(int,input().split())
    graph[u][d] = 1
    
for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            if graph[j][k] == 1 or (graph[j][i] == 1 and graph[i][k] == 1):
                graph[j][k] = 1
                
ans = 0
 
for i in range(1, N+1):
    tmp = 0
    for j in range(1, N+1):
        tmp += graph[i][j] + graph[j][i]
        
    if tmp == N-1:
        ans += 1
 
print(ans)

 

1956 운동

import sys
 
input = sys.stdin.readline
 
V, E = map(int, input().split())
INF = int(1e9)
distance = [[INF]*(V+1) for _ in range(V+1)]
 
for _ in range(E):
    x, y, c = map(int, input().split())
    distance[x][y] = c
    
for i in range(1, V+1):
    for j in range(1, V+1):
        for k in range(1, V+1):
            if distance[j][k] > distance[i][k] + distance[j][i]:
                distance[j][k] = distance[j][i] + distance[i][k]
                
ans = INF
 
for i in range(1, V+1):
    ans = min(ans, distance[i][i])
    
if ans == INF:
    print(-1)
else:
    print(ans)

 

 

14938 서강그라운드

import sys
 
input = sys.stdin.readline
 
INF = int(1e9)
 
n, m, r = map(int, input().split())
 
items = list(map(int, input().split()))
 
dist = [[INF] * n for _ in range(n)]
 
for _ in range(r):
    s, e, d = map(int, input().split())
    dist[s-1][e-1] = min(dist[s-1][e-1], d)
    dist[e-1][s-1] = min(dist[e-1][s-1], d)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
            if j == k:
                dist[j][k] = 0
                
ans = 0
 
for i in range(n):
    tmp = 0
    for j in range(n):
        if dist[i][j] <= m:
            tmp += items[j]
            
    ans = max(ans, tmp)
    
print(ans)

얘도 패턴이있넹