[백준] 2307번 도로검문 파이썬
문제
그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다.
그림 1
예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다.
어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하려고 한다. 따라서 용의자는 이 도로를 피해서 가장 빠르게 도시를 탈출하고자 한다. 이 경우 경찰이 검문을 위하여 선택하는 도로에 따라서 용의자의 가장 빠른 탈출시간은 검문이 없을 때에 비하여 더 늘어날 수 있다.
문제는 도로검문을 통하여 얻을 수 있는 탈출의 최대 지연시간을 계산하는 것이다. 추가설명은 다음과 같다.
- 두 개의 지점을 직접 연결하는 도로가 있는 경우, 그 도로는 유일하다.
- 도시의 지점(노드)은 1에서 N번까지 N개의 연속된 정수로 표시된다.
- 용의자가 도시에 진입하는 지점은 항상 1번이고 도시를 빠져 나가기 위하여 최종적으로 도달해야하는 지점은 항상 N번 지점이다.
- 용의자는 검문을 피해서 가장 빨리 도시를 빠져나가고자 하고, 경찰은 적절한 도로를 선택하여 이 용이자들의 탈출시간을 최대한 지연시키고자 한다.
- 각 도시 지점 간을 이동하는 시간은 항상 양의 정수이다.
입력 도시의 도로망에 따라서 경찰이 어떤 도로를 막으면 용의자는 도시를 탈출하지 못할 수도 있다. 이 경우 검문으로 인하여 지연시킬 수 있는 탈출시간은 무한대이다. 이 경우에는 -1을 출력해야 한다.
그림 1에서 볼 때 검문이 없을 경우 용의자가 도시를 탈출하는데 걸리는 시간은 4분이다. 만일 경찰이 도로(4,3)을 막으면 그 탈출시간을 지연시킬 수 없으므로 지연시간은 0이다. 만일 도로(2,3)을 막으면, 용의자들이 가장 빠르게 탈출할 수 있는 시간은 5분이므로 탈출지연시간은 1분이고, 도로(3,6)을 막으면 탈출지연시간은 2분이다.
여러분은 입력 데이터에 표시된 도로망을 읽고, 경찰이 한 도로를 막고 검문함으로써 지연시킬 수 있는 최대시간을 정수로 출력하여야한다. 만일 지연효과가 없으면 0을 출력해야하고, 도시를 빠져나가지 못하게 만들 수 있으면(지연시간이 무한대) -1을 출력해야 한다.
입력
첫 줄에는 지점의 수를 나타내는 정수 N(6 ≤ N ≤ 1000)과 도로의 수 M(6 ≤ M ≤ 5000)이 주어진다. 그 다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 ≤ t ≤ 10000이다.
출력
경찰이 하나의 도로를 막음으로써 지연시킬 수 있는 최대 시간을 정수로 출력한다. (단, 그 지연시간이 무한대이면 -1을 출력해야 한다.)
예제 입력 1
6 7
1 2 1
1 4 3
3 6 1
4 5 1
2 3 2
3 4 1
5 6 2예제 출력 1
2예제 입력 2
8 11
1 2 1
1 5 8
1 7 9
2 5 2
3 4 4
3 6 3
3 8 5
4 6 10
4 8 11
5 6 6
5 7 7예제 출력 2
-1제출 답안
- 최단 거리를 구한다.
- 그 최단 거리가 된 경로를 n부터 역행하며 새로운 리스트에 담는다.
- 그래야 지연에 효과적인지 알 수 있다.
- 최단거리 좌표를 하나씩 제거하면서 최단거리를 구한다.
- 여기서 a,b를 edges에서 remove하는 것보다 visited로 방문 여부를 활용하는게 효율적이라 생각했다.
- 마지막으로 result에 따라 결과를 출력한다.
'''
1. 아이디어
- 최단거리 구하기
- n부터 역행으로 최단거리가 어디인지 조사한 결과 담기
- 최단거리를 제거하면서 지연시간 찾기
2. 시간 복잡도
- ElogV
- 5000*10 = 50,000 < 2억
3. 변수
edge = [][]
distance = []
visited = [][]
'''
import sys
import heapq
from collections import deque
input = sys.stdin.readline
INF = sys.maxsize
n, m = map(int, input().split())
edge = [[] for _ in range(n+1)]
for _ in range(m):
a, b, t = map(int, input().split())
edge[a].append((t, b))
edge[b].append((t, a))
def dijkstra(visited) -> list[int]:
dist = [INF] * (n+1)
dist[1] = 0
heap = [(0, 1)]
while heap:
ew, ev = heapq.heappop(heap)
if dist[ev] < ew : continue
for nw, nv in edge[ev]:
if visited[ev][nv] or visited[nv][ev]: continue
visited[ev][nv] = True
visited[nv][ev] = True
sun_w = ew + nw
if dist[nv] > sun_w:
dist[nv] = sun_w
heapq.heappush(heap, (sun_w, nv))
return dist
visited = [[False] * (n+1) for _ in range(n+1)]
dist = dijkstra(visited)
def bfs():
nodes = []
q = deque([n])
while q:
node = q.popleft()
if node == 1:
continue
for pw, pv in edge[node]:
if dist[pv] + pw == dist[node]:
nodes.append((pv, node, pw))
q.append(pv)
return nodes
nodes = bfs()
distance = dist[n]
result = 0
for node in nodes:
a, b, t = node
visited = [[False] * (n+1) for _ in range(n+1)]
visited[a][b] = True
visited[b][a] = True
dist = dijkstra(visited)
if dist[n] == INF :
result = dist[n]
result = max(result, dist[n] - distance)
print(-1 if result == INF else result)