07735: 道路

http://cs101.openjudge.cn/practice/07735/

同 01724: ROADS，Dijkstra, dfs with pruning, http://cs101.openjudge.cn/practice/01724/

import heapq
from collections import defaultdict

MAX_COINS = int(input())  # 最大金币数
CITY_COUNT = int(input())  # 城市数目
ROAD_COUNT = int(input())

# 存储道路信息的字典，使用 defaultdict 初始化
roads = defaultdict(list)

for _ in range(ROAD_COUNT):
    start, end, length, money = map(int, input().split())
    start, end = start - 1, end - 1
    roads[start].append((end, length, money))

def bfs(start, end, max_coins):
    queue = [(0, max_coins, start)]  # (距离, 剩余金币, 当前城市)
    visited = set()

    while queue:
        distance, coins, city = heapq.heappop(queue)

        if city == end:
            return distance

        visited.add((city, coins))

        for next_city, road_length, road_money in roads[city]:
            if coins >= road_money:
                new_distance = distance + road_length
                if (next_city, coins - road_money) not in visited:
                    heapq.heappush(queue, (new_distance, coins - road_money, next_city))

    return -1

print(bfs(0, CITY_COUNT - 1, MAX_COINS))

思路：要在Dijkstra算法的基础上实现剪枝，我们用一个数组记录到当前节点的最小费用（初始为无穷大），若优先队列弹出的元素满足费用大于最小费用，则该节点之前一定被访问过，且存在一种走法比当前走法费用和长度都小。故这个元素一定是无效的，可以舍去，从而实现了剪枝。

题解中直接删去visited检查也可以。但理论上内存应该会更大。

# 应硕丞 数学科学学院
import heapq
k = int(input())
n = int(input())
r = int(input())
graph = {i:[] for i in range(1, n+1)}
for _ in range(r):
    s, d, dl, dt = map(int, input().split())
    graph[s].append((dl,dt,d))
que = [(0,0,1)]
fee = [10000]*101
def dijkstra(g):
    while que:
        l, t, d = heapq.heappop(que)
        if d == n:
            return l
        if t>fee[d]:
            continue
        fee[d] = t
        for dl, dt, next_d in g[d]:
            if t+dt <= k:
                heapq.heappush(que,(l+dl, t+dt, next_d))
    return -1
print(dijkstra(graph))

思路：dijkstra变体，要删去visited检查。

#何秉儒 物理学院
import heapq

def dijkstra(g):
    while pq:
        dist,node,fee = heapq.heappop(pq)
        if node == n-1 :
            return dist
        for nei,w,f in g[node]:
            n_dist = dist + w
            n_fee = fee + f
            if n_fee <= k:
                dists[nei] = n_dist
                heapq.heappush(pq,(n_dist,nei,n_fee))
    return -1

k,n,r = int(input()),int(input()),int(input())
g = [[] for _ in range(n)]
for i in range(r):
    s,d,l,t = map(int,input().split())
    g[s-1].append((d-1,l,t)) #node,dist,fee

pq = [(0,0,0)] #dist,node,fee
dists = [float('inf')] * n
dists[0] = 0
spend = 0

result = dijkstra(g)
print(result)