请输入您网站的icp备案信息,网上商城建设杭州服务商,黑五类广告推广,北京网上推广P4568 [JLOI2011] 飞行路线 pytho解析
时间#xff1a;2023.11.20 题目地址#xff1a;[JLOI2011] 飞行路线
题目分析
对于这个题呢就是最短路的问题了。那就可以用Dijkstra 算法#xff0c;唯一不同的地方就是有免费的机票次数#xff0c;那我们就先不考虑这个#xf…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)]*(k1) for _ in range(n)] # 引入cnt
vis set()
pq.put((0, s, 0)) # 初始cnt为0
for i in range(k1):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][nowcnt1] ans[u][nowcnt]:ans[v][nowcnt1] ans[u][nowcnt]pq.put((ans[v][nowcnt1], v, nowcnt1))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]))
