플로이드

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

"""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()

• Dependency: teflib.graph.all_pairs_shortest_paths