[백준/Python] 1238번 : 파티

문제

https://www.acmicpc.net/problem/1238

1238번: 파티

---

풀이

특정 시작점에서 다른 모든 정점으로 가는 최단 거리를 구해주는 알고리즘인 다익스트라를 이용하여 구현한다.

문제는 다른 모든 마을에서 파티가 열리는 마을로 가는 최단 거리와 돌아오는 최단 거리를 구해야 한다.
- 각 마을로 돌아가는 최단 거리는 특정 시작점이 파티가 열리는 마을이므로 
  입력받은 대로 다익스트라를 적용하면 된다.
- 그러나 모든 정점(각 마을)에서 특정점(파티 마을)으로 가는 최단 거리를 구하려면 
  그래프의 모든 간선을 뒤집은 뒤,
  특정점(파티 마을)에서 다른 모든 정점(각 마을)까지 가는 최단 거리를 구하면 된다.

다익스트라 함수를 정의하고, 기존 그래프(graph1)와 모든 간선을 뒤집은 그래프(graph2)를 생성한다.
돌아오는 길(dist1), 가는 길(dist2)의 최단 거리를 저장할 dist배열을 만들고, 특정 시작점 거리를 0으로 한다.
각 그래프에 다익스트라를 적용한 후 결과를 출력한다.

*다익스트라 함수
다익스트라를 구현하기 위해 자동 정렬해 주는 최소 힙을 이용한다. (heapq)
q에 시작점의 정보(거리, 정점)를 push 하고, 빈 q가 아닐 때까지 반복한다. 
최소 힙이므로 pop을 하게 되면 거리가 가장 짧은 정점이 선택되고,
해당 정점에서 인접한 정점들의 거리를 갱신한다.
갱신된 정점을 q에 push 한다.

---

코드

import sys, heapq
input = sys.stdin.readline

def dijkstra(graph, dist):
    q = []
    heapq.heappush(q, (0, x))
    while q:
        d, k = heapq.heappop(q)

        if dist[k] < d:
            continue
        
        for i in graph[k]:
            cost = d + i[1]
            if cost < dist[i[0]]:
                dist[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


n, m, x = map(int, input().split())
graph1 = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph1[a].append((b, c))
    graph2[b].append((a, c))

dist1 = [sys.maxsize] * (n+1)
dist2 = [sys.maxsize] * (n+1)
dist1[x], dist2[x] = 0, 0
dijkstra(graph1, dist1)
dijkstra(graph2, dist2)

ans = 0
for i in range(1, n+1):
    ans = max(ans, dist1[i] + dist2[i])

print(ans)