题解 | 2023_南京理工-最短路径问题_1563

from heapq import heappush, heappop
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, d, p = map(int, input().split())
        graph[a].append([b, d, p])
        graph[b].append([a, d, p])
    s, t = map(int, input().split())
    minDist, minCost = [float("inf")] * (n + 1), [float("inf")] * (n + 1)
    minDist[s] = 0
    minCost[s] = 0
    pq = [(0, 0, s)]
    while pq:
        dist, cost, node = heappop(pq)
        if dist > minDist[node]:
            continue
        for next in graph[node]:
            to = next[0]
            new_dist = minDist[node] + next[1]
            new_cost = minCost[node] + next[2]
            if minDist[to] > new_dist:
                minDist[to] = new_dist
                minCost[to] = new_cost
                heappush(pq, (new_dist, new_cost, to))
            elif minDist[to] == new_dist and minCost[to] > new_cost:
                minCost[to] = new_cost
                heappush(pq, (new_dist, new_cost, to))
    print(minDist[t], minCost[t])