01724: ROADS

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

同 07735: 道路，http://cs101.openjudge.cn/practice/07735/

N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.

We want to help Bob to find the shortest path from the city 1 to the city N that he can affordwith the amount of money he has.

输入

The first line of the input contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2 <= N <= 100, the total number of cities.

The third line contains the integer R, 1 <= R <= 10000, the total number of roads.

Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :

• S is the source city, 1 <= S <= N
• D is the destination city, 1 <= D <= N
• L is the road length, 1 <= L <= 100
• T is the toll (expressed in the number of coins), 0 <= T <=100

Notice that different roads may have the same source and destination cities.

输出

The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, only number -1 should be written to the output.

样例输入

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

样例输出

11

来源

CEOI 1998

#何秉儒 物理学院
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)

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

#23n23000111119(武)
from heapq import heappop, heappush
from collections import defaultdict

K, N, R = int(input()), int(input()), int(input())
graph = defaultdict(list)
for i in range(R):
    S, D, L, T = map(int, input().split())
    graph[S].append((D, L, T))


def Dijkstra(graph):
    global K, N, R
    q, ans = [], []
    heappush(q, (0, 0, 1, 0))  # (length,cost,cur,step)
    while q:
        l, cost, cur, step = heappop(q)
        if cur == N: return l
        for next, nl, nc in graph[cur]:
            if cost + nc <= K and step + 1 < N:
                heappush(q, (l + nl, cost + nc, next, step + 1))
    return -1


print(Dijkstra(graph))

visited记录上次访问时所花费的money，由于我们利用优先队列实现了短的路径优先弹出，如果再次遇到了之前访问过的点，那路径一定更长，因此只有在花费的money更少并且不超出K的情况下才考虑入队，循环操作直至第一次遇到目的地

# 王昊 光华管理学院
import heapq


K, N, R = map(int, [input() for _ in range(3)])
graph = {i: [] for i in range(1, N+1)}
visited = {i: float('inf') for i in range(1, N+1)}
for _ in range(R):
    S, D, L, T = map(int, input().split())
    graph[S].append((D, L, T))

queue, ans = [(0, 0, 1)], -1
while queue:
    l, t, s = heapq.heappop(queue)
    if s == N:
        ans = l
        break
    visited[s] = t
    for d, z, w in graph[s]:
        if t+w < visited[d] and t+w <= K:
            heapq.heappush(queue, (l+z, t+w, d))
print(ans)

# 23n2310307206
import heapq
class edge:
    def __init__(self,start,end,length,money):
        self.start = start
        self.end = end
        self.money = money
        self.length = length
k = int(input())
n = int(input())
r = int(input())
graph = {i:[] for i in range(1,n+1)}
for i in range(r):
    s,d,l,t = map(int,input().split())
    graph[s].append(edge(s,d,l,t))
def dijskra():
    visited=[0]*(n+1)
    ans=-1
    priorQueue=[]
    heapq.heappush(priorQueue,(0,0,1))#length,money,pos
    while priorQueue:
        length,money,pos = heapq.heappop(priorQueue)
        visited[pos] = 1
        if pos == n and money<=k:
            ans=length
            break
        if money > k:

            continue
        for road in graph[pos]:
            pos1 = road.end
            m1 = road.money+money
            l1 = road.length+length
            if m1<=k and visited[pos1] != 1:
                heapq.heappush(priorQueue,(l1,m1,pos1))
        visited[pos] = 0

    print(ans)
dijskra()

Dijkstra

# 23n2000012515(heol)
from heapq import heappush as hu, heappop as hp

k, n, r = [int(input()) for _ in range(3)]
edge, vis = [[] for _ in range(n + 1)], [100000] * (n + 1)

for _ in range(r):
    x, y, z, w = map(int, input().split())
    edge[x].append((y, z, w))

q, ans = [], -1
hu(q, (0, 0, 1))

while q:
    l, c, x = hp(q)
    if x == n:
        ans = l
        break
    vis[x] = c
    for y, z, w in edge[x]:
        if c + w < vis[y] and c + w <= k:
            hu(q, (l + z, c + w, y))

print(ans)

从城市 1开始深度优先遍历整个图，找到所有能过到达 N 的走法，选一个最优的。《算法基础与在线实践》有讲到。

1）可行性剪枝：

提前预判出一条路走下去不可能走到终点，于是就不走了。在本题中，可行性剪枝十分直观，即发现如果往前走一步到达城市i，花掉的路费就会超过总钱数K那么就不去城市i。

2）最优性剪枝：

在用深搜的方法寻找最优路径（代价最小路径）时，“最优性剪枝”是最常用的方法。思想是，如果提前预判出一条路走下去即便能到终点也不可能是最优的，那就不走了。具体实现的办法是，记下已经找到的起点到终点的目前最优路径的代价C，那么在后续搜索其他路径的过程中，如果走到某个结点k时，发现从起点走到k所花的代价已经大于或等于C，那么就应该立即回退，而不是从k出发继续往前走——因为即便再走下去能够到达终点，所花的代价也一定大于或等于C，相当于徒劳地走。

3）处处最优剪枝：

有时仅仅用上述的可行性剪枝和最优性剪枝还是不够高效。还有一种更强的最优性剪枝方案，是记下从起点到每一个结点V的当前最优路径的代价C。下次探索新路径走到V时如果发现所花的代价已经大于或等于C，则这条新路径就没必要从V再走下去了，应立即回退。这又是用空间换时间的技巧。不妨称这种最优性剪枝为“处处最优剪枝”。

在本题中，仅用可行性剪枝和简单的最优性剪枝是不够的，需要用“处处最优剪枝”。本题中路径的“代价”，实际上就是路径的长度。最优路径就是长度最短的路径。但是由于还有过路费的问题，所以不能直接使用“处处最优剪枝”。因为，同是从起点到达结点V的两条路，长的路不一定就比短的路差。有可能长的那条路花费少，往下走可以走到终点，而短的那条路花费太多，往下走走不到终点。 将过路费考虑进去，可以用 min_lengths[i][j]记录，表示走到城市i时，在已花掉的过路费为j的条件下，从城市1到i的最优路径的长度。若在后续的搜索中再次走到i时，已花掉的过路费恰好为 j，且此时的路径长度已经超过 min_lengths[i][j]，则不必再走下去了。

class Road:
    def __init__(self,d,L,t):
       self.d,self.L,self.t = d,L,t


def dfs(s, total_cost, total_length, visited, city_map, min_lengths, k):
    global min_length
    if s == n:
        min_length = min(min_length, total_length)
        return
    for i in range(len(city_map[s])):
        d, L, t = city_map[s][i].d, city_map[s][i].L, city_map[s][i].t
        if visited[d]:
            continue
        cost = t + total_cost
        length = L + total_length
        if cost > k :   # 可行性剪枝：超过预算
            continue
        if (length >= min_length or # 最优性剪枝：超过当前最优解
                length >= min_lengths[d][cost]): # 处处最优性剪枝：超过已经搜索到的最优解
            continue
        min_lengths[d][cost] = length
        visited[d] = True
        dfs(d, cost, length, visited, city_map, min_lengths, k)
        visited[d] = False


k,n,r = int(input()),int(input()),int(input())
city_map = [[] for i in range(n+1)] #邻接表。city_map[i]是从点i有路连到的城市集合
for _ in range(r):
    r = Road(0, 0, 0)
    s, r.d, r.L, r.t = map(int, input().split())
    if s != r.d:
        city_map[s].append(r)
INF = float('inf')
min_length = INF

#min_lengths[i][j]表示从1到i点，花销为j的最短路径的长度
min_lengths = [[INF] * (k + 1) for _ in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
dfs(1, 0, 0, visited, city_map, min_lengths, k)
if min_length < INF:
    print(min_length)
else:
    print(-1)