특정한 최단 경로

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

• Dependency: teflib.graph.dijkstra