테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 플로이드 ======
  * 기본적인 [[ps:APSP]] 문제. 입력으로 들어오는 그래프가 밀집그래프이기 때문에, 문제 제목에서도 알려주듯이 플로이드 알고리즘을 사용해서 푸는 것이 효과적이다. 시간복잡도는 O(V^3)
  * 구현상 실수할만한 부분은
    * 1. 두 도시간에 여러개의 노선이 있을 수 있다 => 최단 노선만 남기고 나머지를 버려서 simple graph로 바꾼 뒤에 계산
    * 2. 경로가 없으면 0으로 출력

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11404. 플로이드".

- Problem link: https://www.acmicpc.net/problem/11404
- Solution link: http://www.teferi.net/ps/problems/boj/11404
"""

import sys
from teflib import graph as tgraph

INF = float('inf')


def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    mat_graph = [[INF] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = [int(x) for x in sys.stdin.readline().split()]
        if c < mat_graph[a - 1][b - 1]:
            mat_graph[a - 1][b - 1] = c

    dist_mat = tgraph.all_pairs_shortest_paths(mat_graph)

    for l in dist_mat:
        print(*(0 if x == INF else x for x in l))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:graph#all_pairs_shortests_paths|teflib.graph.all_pairs_shortest_paths]]
 
{{tag>BOJ ps:problems:boj:골드_4}}