• X에서 각 마을까지 가는 최단 거리와, 각 마을에서 X까지 가는 최단거리를 알면 두개의 합이 가장 큰 마을을 찾는것은 쉽게 할수 있다.
• X에서 각 마을까지 가는 최단 거리는 데이크스트라 알고리즘 (Dijkstra's algorithm)을 돌리면 바로 계산된다. 각 마을에서 X까지 가는 최단거리는, 그래프의 간선 방향을 모두 반대로 해준 다음에 X에서 출발하는 데이크스트라 알고리즘 (Dijkstra's algorithm)을 돌려서 구할수 있다.
• 결국 O(ElogV)의 다익스트라 알고리즘을 두번 돌려야 하고, V개의 마을에 대해서 왕복거리의 합을 계산해서 가장 큰것을 고르는 것은 O(V)에 가능하므로, 총 시간 복잡도는 O(ElogV).

"""Solution code for "BOJ 1238. 파티".

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

Tags: [Dijkstra]
"""

import sys
from teflib import graph as tgraph


def main():
    N, M, X = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(N)]
    rev_wgraph = [{} for _ in range(N)]
    for _ in range(M):
        s, e, T = [int(x) for x in sys.stdin.readline().split()]
        wgraph[s - 1][e - 1] = rev_wgraph[e - 1][s - 1] = T

    times_from_home = tgraph.dijkstra(wgraph, X - 1)
    times_to_home = tgraph.dijkstra(rev_wgraph, X - 1)
    answer = max(x + y for x, y in zip(times_from_home, times_to_home))

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.dijkstra