사용자 도구

사이트 도구


ps:problems:boj:1238

파티

ps
링크acmicpc.net/…
출처BOJ
문제 번호1238
문제명파티
레벨골드 3
분류

다익스트라

시간복잡도O(ElogV)
인풋사이즈V<=1000, E<=10000
사용한 언어Python
제출기록34796KB / 108ms
최고기록72ms
해결날짜2022/09/20

풀이

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

토론

댓글을 입력하세요:
U G K G U
 
ps/problems/boj/1238.txt · 마지막으로 수정됨: 2022/09/20 16:38 저자 teferi