[플로이드워셜] 백준 11404번 '플로이드' (Python)

<문제 링크>

https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

<문제 풀이>

1. 모든 도시에 대한 비용을 구해야 하므로 플로이드 워셜 알고리즘 활용
2. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있으므로, 최소비용인 노선을 그래프에 입력
3. 노선이 없으면 비용을 0으로 처리

<코드>

'''입력 예시
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4
'''

n = int(input())
m = int(input())

graph = [[int(1e9)]*(n+1) for _ in range(n+1)]

for a in range(1,n+1):
	for b in range(1,n+1):
		if a==b:
			graph[a][b] = 0

for i in range(m):
    a,b,c = map(int, input().split())
    if graph[a][b]>c:
        graph[a][b] = c

for k in range(1,n+1):
	for a in range(1,n+1):
		for b in range(1,n+1):
			graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

for a in range(1,n+1):
    for b in range(1,n+1):
        if graph[a][b]<int(1e9):
            print(graph[a][b],end=' ')
        else:
            print(0,end=' ')
    print()

#220325
n = int(input())
m = int(input())

graph = [[1e9]*(n+1) for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        if i==j:
            graph[i][j] = 0
            
for i in range(m):
    a,b,c = map(int,input().split())
    if graph[a][b] > c:
        graph[a][b] = c

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j] == 1e9:
            print(0, end=' ')
        else:
            print(graph[i][j], end=' ')
    print()

 

<고쳐야 할 점>

• 노드 간에 갈 수 없는 경우를 항상 생각해야 함