사용자 도구

사이트 도구


ps:problems:boj:1504

특정한 최단 경로

ps
링크acmicpc.net/…
출처BOJ
문제 번호1504
문제명특정한 최단 경로
레벨골드 4
분류

다익스트라

시간복잡도O(ElogV)
인풋사이즈V<=800, E<=200,000
사용한 언어Python
제출기록58280KB / 388ms
최고기록344ms
해결날짜2022/09/16

풀이

  • S에서 E까지 가는 동안 x와 y를 거쳐야 한다. 그렇다면 S→x→y→E 로 가거나 S→y→x→E 로 가는 두가지중 하나이므로, 둘중에서 짧을쪽을 택하면된다.
  • 이를 계산하려면 S-x, x-y, y-E, S-y, x-E 사이의 거리를 알아야 하는데, 이는 다익스트라 알고리즘을 시작점을 x로 놓고 한번 돌리고, y로 놓고 한번 돌려서 총 2번 돌리면 얻을수 있다.
  • 시간복잡도는 O(ElogV)
  • 이 문제는 N이 최대 800, 양방향 엣지가 최대 200,000으로 주어지므로, 이정도면 꽤나 dense한 그래프라고 생각해서, 힙을 사용하지 않는 O(V^2)의 다익스트라 알고리즘으로도 도전해보았다. 열심히 최적화해서 O(ElogV)의 다익스트라와 거의 비슷한 속도를 내는데까지는 왔지만, 더 빨라지지는 못했다 (힙: 388ms vs 리스트 392ms). 다만 O(V^2) 다익스트라쪽이 메모리면에서 효율적이라는 것은 확인했다 (힙: 58240KB vs 리스트 38084ms)

코드

"""Solution code for "BOJ 1504. 특정한 최단 경로".

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

Tags: [Dijkstra]
"""

import sys
from teflib import graph as tgraph

INF = float('inf')


def main():
    N, E = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(N)]
    for _ in range(E):
        a, b, c = [int(x) for x in sys.stdin.readline().split()]
        wgraph[a - 1][b - 1] = wgraph[b - 1][a - 1] = c
    v1, v2 = [int(x) for x in sys.stdin.readline().split()]

    dist_from_v1 = tgraph.dijkstra(wgraph, v1 - 1)
    dist_from_v2 = tgraph.dijkstra(wgraph, v2 - 1)
    dist = dist_from_v1[v2 - 1] + min(dist_from_v1[0] + dist_from_v2[N - 1],
                                      dist_from_v2[0] + dist_from_v1[N - 1])

    print('-1' if dist == INF else dist)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
G​ W​ X​ Q Y
 
ps/problems/boj/1504.txt · 마지막으로 수정됨: 2022/09/19 08:42 저자 teferi