原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376
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
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