[최단 경로] 백준 1238번: 파티 / 골드 3

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

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

import collections
import heapq
n, m, x = map(int, input().split())

graph = collections.defaultdict(list)
for i in range(m):
    u,v,w = map(int, input().split())
    graph[u].append([v,w])

# go back to home
start = [0,x] # cost, node
dist = {}
q = []
heapq.heappush(q, start)
while q:
    cost, node = heapq.heappop(q)
    if node not in dist:
        dist[node] = cost
        for next, w in graph[node]:
            heapq.heappush(q, [w+cost, next])

# go to party
for i in range(1,n+1):
    if i == x:
        continue
    start = [0, i]  # cost, node
    dist2 = {}
    q = []
    heapq.heappush(q, start)
    while q:
        cost, node = heapq.heappop(q)
        if node not in dist2:
            dist2[node] = cost
            if node == x: # stop
                break
            for next, w in graph[node]:
                heapq.heappush(q, [w + cost, next])
    dist[i] += dist2[x]

print(max(dist.values()))

다익스트라로 풀 수 있다.

a->b->a 의 최단 경로 중 가장 큰 값을 찾는 것이므로 간략히 하자면

다익스트라 결과 두 개를 더해주면 된다.