解题思路:
注意事项:
参考代码:
import heapq
N=100010
e=[0]*N
ne=[0]*N
w=[0]*N
h=[-1]*N
index=0
st=[False]*N
def add(a,b,c):
global index
e[index]=b
w[index]=c
ne[index]=h[a]
h[a]=index
index+=1
def dijkstra():
dis=[float('inf')]*(n+1)
dis[1]=0
heap=[]
heapq.heappush(heap,(dis[1],1))
while heap:
t=heapq.heappop(heap)
distance,ver=t[0],t[1]
if st[ver]==True:
continue
st[ver]=True
i=h[ver]
while i!=-1:
j=e[i]
if dis[j]>distance+w[i]:
dis[j]=distance+w[i]
heapq.heappush(heap,(dis[j],j))
i=ne[i]
if dis[n]==float('inf'): return -1
else:return dis[n]
n,m=map(int,input().split())
for i in range(m):
a,b,c=map(int,input().split())
add(a,b,c)
add(b,a,c)
print(dijkstra())
0.0分
0 人评分
【蟠桃记】 (C语言代码)浏览:666 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:745 |
【绝对值排序】 (C语言代码)浏览:825 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1466 |
模拟计算器 (C语言代码)浏览:2301 |
格式化数据输出 (C语言代码)浏览:822 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:2166 |
用getchar()函数接收字符,正序输入为什么会倒序输出浏览:741 |
求教大神。。。。1063,统计字符。浏览:11685 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:486 |