洛谷 P4568 [JLOI2011] 飞行路线 pytho解析

P4568 [JLOI2011] 飞行路线 pytho解析

时间：2023.11.20
题目地址：[JLOI2011] 飞行路线

题目分析

对于这个题呢就是最短路的问题了。那就可以用Dijkstra 算法，唯一不同的地方就是有免费的机票次数，那我们就先不考虑这个，就当次数为0。见代码①。这样就是一个比较模板的最短路问题了。
那现在要考虑到有免费的次数，那么就要将ans数组进行改变，引入一个次数即可，见代码②。看看代码的变化，理解清楚即可。
但是提交超时了，呃，只能说python是这样的，哈哈哈哈哈。
重在理解思路。

代码

① 假设免费机票次数为0

from queue import PriorityQueue

n, m, k = map(int, input().split())
s, t = map(int, input().split())
e = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    e[a].append((b, c))
    e[b].append((a, c))
    
pq = PriorityQueue()
ans = [float('inf')]*n
vis = set()
pq.put((0, s))
ans[s] = 0
while not pq.empty():
    _, u = pq.get()
    if u in vis:
        continue
    vis.add(u)
    for v, w in e[u]:
        if ans[v] > ans[u] + w:
            ans[v] = ans[u] + w
            pq.put((ans[v], v))

print(ans[t])     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

② 超时，过70%

from queue import PriorityQueue

n, m, k = map(int, input().split())
s, t = map(int, input().split())
e = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    e[a].append((b, c))
    e[b].append((a, c))
    
pq = PriorityQueue()
ans = [[float('inf')]*(k+1) for _ in range(n)]  # 引入cnt
vis = set()
pq.put((0, s, 0))     # 初始cnt为0
for i in range(k+1):
    ans[s][i] = 0
while not pq.empty():
    _, u, nowcnt = pq.get()
    if (u, nowcnt) in vis:
        continue
    vis.add((u,nowcnt))
    for v, w in e[u]:
        if nowcnt < k and ans[v][nowcnt+1] > ans[u][nowcnt]:
            ans[v][nowcnt+1] = ans[u][nowcnt]
            pq.put((ans[v][nowcnt+1], v, nowcnt+1))
        if ans[v][nowcnt] > ans[u][nowcnt] + w:
            ans[v][nowcnt] = ans[u][nowcnt] + w
            pq.put((ans[v][nowcnt], v, nowcnt))

print(min(ans[t]))     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30