[ baekjoon ] 골목 대장 호석 - 효율성2 20183번 ( python )

문제

백준 20183 골목 대장 호석 - 효율성2 풀이 ( 파이썬 )

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

20183번: 골목 대장 호석 - 효율성 2

 

풀이

처음에는 dfs로 도전했지만 시간초과 문제를 해결 못했고, 다익스트라로 해결하기로 했다. 

이진탐색으로 mid가 최대값이라고 가정했을 때 갈 수 있는가 판단해서 찾는다.

import heapq
import sys

input=sys.stdin.readline

n,m,a,b,c=map(int,input().split())
INF=int(1e14)+1
graph=[[] for _ in range(n)]

def dijkstra(mid):
    pq=[]
    cost=[INF]*(n+1)
    heapq.heappush(pq,(0,a))
    cost[a] = 0
    while pq:
        cos,cur=heapq.heappop(pq)
        if cost[cur] != cos:
            continue
        for i in graph[cur]:
            nxt,cst=i
            if cst>mid:
                continue
            if cost[nxt]>cost[cur]+cst :
                cost[nxt]=cost[cur]+cst
                if nxt==b and cost[nxt]<=c:
                    return True
                heapq.heappush(pq,(cost[nxt],nxt))
    return cost[b]<=c

# 0 index로 하기위해서
a-=1
b-=1
costs = []
for i in range(m):
    s,e,d=map(int,input().split())
    s-=1
    e-=1
    graph[s].append((e,d))
    graph[e].append((s,d))
    heapq.heappush(costs,-d)

costs = sorted(costs)
L=0
R=-heapq.heappop(costs)
ans=INF
while L<=R:
    mid=(L+R)//2
    if dijkstra(mid):
        ans=min(ans,mid)
        R=mid-1
    else:
        L=mid+1

if ans==INF:
    print(-1)
else:
    print(ans)