사용자 도구

사이트 도구


ps:problems:boj:11404

플로이드

ps
링크acmicpc.net/…
출처BOJ
문제 번호11404
문제명플로이드
레벨골드 4
분류

그래프, 전체쌍 최단경로

시간복잡도O(V^3+E)
인풋사이즈V<=100, E<=100,000
사용한 언어Python 3.11
제출기록32140KB / 204ms
최고기록204ms
해결날짜2024/03/11
  • 기본적인 전체쌍 최단 경로 문제 (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()

토론

댓글을 입력하세요:
F V F Z C
 
ps/problems/boj/11404.txt · 마지막으로 수정됨: 2024/03/14 08:33 저자 teferi