本文主要是介绍洛谷 P4568 [JLOI2011] 飞行路线 pytho解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
P4568 [JLOI2011] 飞行路线 pytho解析
时间:2023.11.20
题目地址:[JLOI2011] 飞行路线
题目分析
对于这个题呢就是最短路的问题了。那就可以用Dijkstra 算法,唯一不同的地方就是有免费的机票次数,那我们就先不考虑这个,就当次数为0。见代码①。这样就是一个比较模板的最短路问题了。
那现在要考虑到有免费的次数,那么就要将ans数组进行改变,引入一个次数即可,见代码②。看看代码的变化,理解清楚即可。
但是提交超时了,呃,只能说python是这样的,哈哈哈哈哈。
重在理解思路。
代码
① 假设免费机票次数为0
from queue import PriorityQueuen, 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:continuevis.add(u)for v, w in e[u]:if ans[v] > ans[u] + w:ans[v] = ans[u] + wpq.put((ans[v], v))print(ans[t])
② 超时,过70%
from queue import PriorityQueuen, 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:continuevis.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] + wpq.put((ans[v][nowcnt], v, nowcnt))print(min(ans[t]))
这篇关于洛谷 P4568 [JLOI2011] 飞行路线 pytho解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!