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算法进行求解

 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