[파이썬] 백준 2325 : 개코전쟁 (플레5)

[파이썬] 백준 2325 : 개코전쟁 (플레5)

• https://www.acmicpc.net/problem/2325

 

---

풀이

방향성 생각

• N = 1000, M=50000
• 간선이 최대 50000개 존재하기 때문에, $O((ElogV)^2)$로는 풀이가 불가능하다.
• 다익스트라를 통해 최소 경로를 찾아주고, 그 경로를 무시했을 때 걸리는 시간을 기록한다.
• $O(V*ElogV)$ = $O(NMlogN)$이다.
• 다른 플레 하위 그래프 문제에서도 비슷한 결의 문제가 많다.

 

---

전체코드

import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))
    G[b].append((a,cost))

# shortcut을 먼저 찾아준다. 역추적 해야하니 V에 시간,이전노드 기록
def find_path():
    V = [[float('inf'),-1]]*(N+1)
    V[1][-1] = 0
    heap = [(0,1)]
    while heap:
        t,x = hq.heappop(heap)
        for nx,cost in G[x]:
            nt = t+cost
            if nt < V[nx][0]:
                V[nx] = (nt,x)
                hq.heappush(heap,(nt,nx))
    # 역추적 N번 -> 1번
    path = [N]
    while path[-1] != 1:
        path.append(V[path[-1]][1])
    return path

# 특정 edge 받았을 때, 그 edge를 무시하는 다익스트라
def di(edge):
    V = [float('inf')]*(N+1)
    V[1] = 0
    heap = [(0,1)]
    while heap:
        t,x = hq.heappop(heap)
        for nx,cost in G[x]:
            if edge == [x,nx] or edge == [nx,x]:
                continue
            nt = t+cost
            if nt < V[nx]:
                V[nx] = nt
                hq.heappush(heap,(nt,nx))
    return V[N]

shortcut = find_path()
answer = [di(shortcut[i:i+2]) for i in range(len(shortcut)-1)]
print(max(answer))

 

---

코멘트

• .