[백준] 2307 도로검문 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/2307
• 🔑 다익스트라, 최단 경로 저장
  • 처음에 n개의 노드를 하나씩 다 막아봤다. (그래도 풀리긴 함)
  • 그다음에는 용의자가 이동하는 최단 경로만 검문을 해서 시간을 줄였다. 2316ms → 852ms
  • 최단 경로를 딕셔너리 형식으로 저장 ex) 6 : 3 이면 3을 지나서 6으로 감
  • 이렇게 저장해서 해당 경로를 매개 변수로 넘겨주고 이쪽 경로로는 못 가게 조건 추가
  • 최단 경로를 전부 검문해 보고 용의자가 탈출하는데 가장 오래 걸리는 시간을 구하면 끝 ✨

 

import sys
from collections import defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline

n, m = map(int, input().split())

graph = defaultdict(list)

for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a].append((t, b))
    graph[b].append((t, a))

start, end = 1, n
INF = int(1e9)
path = {}   # 최단 경로 저장

def dijkstra(i, x):
    distance = [INF] * (n+1)
    distance[i] = 0

    q = [(0, i)]

    while q:
        now_d, now = heappop(q)

        if distance[now] < now_d: 
            continue

        for next_d, next in graph[now]:
            new_d = now_d + next_d
            if next != x and distance[next] > new_d:
                distance[next] = new_d
                if x == -1:
                    path[next] = now
                heappush(q, (new_d, next))

    return distance

D = dijkstra(start, -1) # 경찰이 안 막았을 때 (-1)

answer = -1
x = n
while path[x] != start: # 최단 경로만 하나씩 막아본다.
    d = dijkstra(start, path[x])
    if d[n] == INF:
        print(-1)
        exit()
    answer = max(answer, d[n] - D[n])
    x = path[x]

print(answer)