PAT-1003 Emergency (25 分) python 图论-最短路
2021/7/17 22:05:48
本文主要是介绍PAT-1003 Emergency (25 分) python 图论-最短路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4
题解:指定目标点,属于单元最短路径问题,因此可以用Dijkstra算法进行求解
![](/images/baidian.png)
1 INF=100000000 2 weight,num,w,vis,d=[0]*505,[0]*505,[0]*505,[0]*505,[INF]*505 3 G=[[INF]*505 for _ in range(505)] 4 5 def Dijkstra(st): 6 d[st]=0 7 w[st]=weight[st] # w:点权之和 weight:each city weight 8 num[st]=1 # 最短路径条数 9 for i in range(n): 10 u,MIN=-1,INF 11 for j in range(n): 12 if vis[j]==0 and d[j]<MIN: 13 u=j 14 MIN=d[j] 15 if u==-1: return 16 vis[u]=1 #标记被访问 17 for v in range(n): 18 if vis[v]==0 and G[u][v]!=INF: 19 if d[u]+G[u][v]<d[v]: 20 d[v]=d[u]+G[u][v] 21 w[v]=w[u]+weight[v] 22 num[v]=num[u] 23 elif d[u]+G[u][v]==d[v]: 24 if w[u]+weight[v]>w[v]: 25 w[v]=w[u]+weight[v] 26 num[v]+=num[u] 27 28 29 if __name__=="__main__": 30 n,m,st,ed=input().split() 31 n,m,st,ed=int(n),int(m),int(st),int(ed) 32 wt=list(map(int, input().split())) 33 for i in range(len(wt)): 34 weight[i]=wt[i] 35 # print(weight[:10]) 36 for i in range(m): 37 u,v,w1=input().split() 38 u,v,w1=int(u),int(v),int(w1) 39 G[u][v],G[v][u]=w1,w1 40 Dijkstra(st) 41 # print(num[:10]) 42 # print(w[:10]) 43 print(num[ed],w[ed])View Code
这篇关于PAT-1003 Emergency (25 分) python 图论-最短路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python