백준 5822 - 악어의 지하 도시 [Python]

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

5822번: 악어의 지하 도시

 

- 다익스트라?

 

문지기의 입장에서 생각해보자.

철수가 갈 수 있는 정점들 중, 가장 가까운 정점으로 가는 간선을 막는 것이 이득이다.

그러므로, 철수는 항상 두번째로 빠른 길로 가게 될 것이다.

 

다익스트라 비슷한 거를 탈출방부터 진행하면 된다.

답은 정점 0에 저장된 두 번째로 먼 길이가 된다.

 

import sys, math
import heapq
 
from collections import deque
input = sys.stdin.readline
 
#input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
############### Main! ###############
 
MAX = 100003
INF = 10 ** 9 + 9
 
n, m, k = mip()
g = [[] for _ in range(MAX)]
d = [INF] * MAX
dd = [INF] * MAX
v = [False] * MAX
 
for i in range(m):
    ai, bi, ci = mip()
    g[ai].append((bi, ci))
    g[bi].append((ai, ci))
 
hq = []
for i in range(k):
    x = ip()
    d[x] = 0
    dd[x] = 0
    heapq.heappush(hq, (0, x))
 
while hq:
    c, x = heapq.heappop(hq)  # cost c, vertex x
    if v[x]:
        continue
    v[x] = True
    for i, j in g[x]:
        if v[i]:
            continue
        if d[i] > dd[x] + j:
            dd[i] = d[i]
            d[i] = dd[x] + j
            if dd[i] < INF:
                heapq.heappush(hq, (dd[i], i))
        elif dd[i] > dd[x] + j:
            dd[i] = dd[x] + j
            heapq.heappush(hq, (dd[i], i))
 
print(dd[0])
 
######## Priest W_NotFoundGD ########