用python实现朴素的dijkstra

• 可用优先队列优化

#python实现朴素的dijkstra
#from Queue import PriorityQueue as pq
INF=0x3f3f3f3f
vis=[False for i in range(2510)]
mp=[[INF for i in range(2510)]for i in range(2510)]
dist=[INF for i in range(2510)]
#qe=pq()
def dijkstra(s,n):
    for i in range(n):
        dist[i]=INF
        vis[i]=False
    dist[s]=0
    while True:
        v=-1
        for i in range(n):
            if vis[i]==0 and (v==-1 or dist[i]<dist[v]):
                v=i
        if v==-1:
            return 
        vis[v]=True
        for i in range(n):
            dist[i]=min(dist[i],dist[v]+mp[v][i])
while True:
    try:
        n,k,s,t=map(int,input().split())
        for i in range(k):
            u,v,w=map(int,input().split())
            mp[u-1][v-1]=min(mp[u-1][v-1],w)
            mp[v-1][u-1]=min(mp[v-1][u-1],w)
        dijkstra(s-1,n)
       # for i in range(n):
        print(dist[t-1])
    except EOFError:
        break