[Algorithm🧬] 백준 5917 : Roadblock

문제

문제

매일 아침, 농부 존은 일어나면 집에서 농장을 가로질러 헛간으로 걸어갑니다. 농장은 N(1≤N≤100)개의 필드로 구성되어 있으며 필드들은 각각의 길이를 갖는 M(1≤M≤10,000)개의 양방향 경로로 연결되어있다. 농부 존의 집은 필드 1이고, 헛간은 필드 N이다. 필드간에 여러 개의 중복 경로는 존재하지 않는다. 농장 안의 필드들 사이를 적절한 순서에 따라 경로를 도보로 이동할 수 있다. 한 필드에서 다른 필드로 이동할 때, 농부 존은 항상 최소한의 전체 길이를 갖는 경로를 선택한다. 즉, 최단경로로 이동한다.


농부 존의 소는 존의 아침 경로를 방해하기로 결정했다. 그들의 계획은 M개의 경로 중 정확히 한 경로에 건초 더미를 쌓아서 그 경로의 길이를 두 배로 바꾸려고 한다. 소는 평소에 농부 존이 선택한 집에서 헛간까지의 최단경로 길이보다 최대한 증가되도록 하는 경로에 설치하고 싶다. 소들이 농부 존의 최단 경로 길이를 얼마나 연장 시킬 수 있는지 계산하시오.

입력

첫 줄에 N(1≤N≤100)과 M(1≤M≤10,000)이 공백으로 구분되어 주어진다.
두 번째 줄부터 M 줄에 걸쳐 A(출발 필드 번호, 1≤A≤N), B(도착 필드 번호, 1≤B≤N), L(A와B 사이의 길이, 1≤L≤1,000,000)가 공백으로 구분되어 주어진다.

출력

한 경로의 길이를 두 배로 했을 때 농부 존의 최단 경로 총 길이를 증가시킬 수 있는 최대값을 출력하시오.
즉 새로운 경로 총 길이 – 기존 경로 총 길이 값임.

처음에
1. 일단 최단경로 구해야 차이를 알겠군 -> 최단경로 구하자
a. 여기서 init 함수에서 roads += 로 했다가 계속 roads 크기가 늘어나서 우여곡절이 많았다....
2. 각 엣지를 두배 해서 최단경로 차이를 알아보자 -> 타임리밋.
a. -> 생각해보니 최단경로 일때 지나오지 않은 길은 2배로 늘려봤자 최단경로에 영향이 없으므로 늘려볼 필요가 없음. 빼자

성공!!

import sys
from collections import deque
import math
readl = sys.stdin.readline

def init(roads):
    # 길은 양방향이니까 시작 - 끝 뒤집어서 저장.
    newRoads = roads + [[end, start, dist] for start, end, dist in roads]
    
    dict = {x[0]: [] for x in newRoads}
    for start, end, dist in newRoads:
        dict[start].append((end, dist))
    
    dists = [math.inf] * (N + 1)

    return dict, dists


def BFS():
    global dict, dists

    # 집은 1
    q = deque([(1, 0)])
    dists[1] = 0

    while q:
        x, dist = q.popleft()

        for nx, d in dict[x]:
            nd = dist + d

            if dists[nx] <= nd:
                continue

            dists[nx] = nd
            q.append((nx, nd))
            temppath[nx] = x

    # 목적지는 N
    return dists[N]

N, M = map(int, readl().split())
roads = [list(map(int, readl().split())) for _ in range(M)]

dict, dists = init(roads)
temppath = [0] * (N + 1)

# 길을 바꾸지 않았을 때 최단거리.
first_min = BFS()

path = []
dest = N
i = temppath[N]
while i > 0:
    path.append((i, dest))
    dest = i
    i = temppath[i]

# 갔던 엣지 저장
path = path[::-1]

# 길을 하나씩 2배로 바꿨을 때 최단거리.
max_of_second_min = 0

# 전체를 다 두배로 바꿀 필요는 없음.
# 원래 최단거리에 포함되는 길만 바꾸면 됨.
for i in range(M):
    start, end, dist = roads[i]

    # 갔던 엣지만 바꾸면 됨.
    if (start, end) in path or (end, start) in path:
        roads[i][2] *= 2

        dict.clear()
        dict, dists = init(roads)

        # b = BFS()
        # print(b)
        max_of_second_min = max(max_of_second_min, BFS())
        

        roads[i][2] /= 2

print(int(max_of_second_min - first_min))