题解 | #游游出游#

以重量作为第一关键字入堆，随后跑dij单源最短路算法，时间复杂度O(nlogw)

import heapq
n,m,h = map(int,input().split())
graph = [[] for _ in range(n+1)]
p = [(0,1,float('inf'))]
p = [(-float('inf'),1,0)]
dist = [0]*(n+1)
for _ in range(m):
    u,v,w,d = map(int,input().split())
    graph[u].append((v,w,d))
    graph[v].append((u,w,d))
while p:
    res,node,dis = heapq.heappop(p)
    res *= -1
    if res > dist[node]:
        dist[node] = res
        for nxt,weight,d in graph[node]:
            if dis + d > h:
                continue
            else:
                heapq.heappush(p,(-min(res,weight),nxt,dis+d))
print(dist[-1] if dist[-1] != 0 else -1)