单源最短路径上的最大值

这里用SPFA(python的SPFA我一直感觉比优先队列dijkstra快一点…，可能是错觉)

单源最短路模板，结果求一个最大值，最大值无限大则传不了输出-1

python版本

推销一下下面的个人发明建边函数def Lin(a,b,c)（我称之为琦氏建边法），速度虽然比纯append来的慢，但是可以稳定的去重边和取最优重边，给用python写图论的兄弟们安利一下=_+

#SPFA算法
def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] = min(link[a][b],c)

def SPFA(start):
    queue = [start]
    inq = [False]*(n+1)  #判断是否在队列中
    dis = [float('inf')]*(n+1)
    dis[start] = 0
    inq[start] = True     #这是优化点，避免重复入队
    while queue:

        curNode = queue.pop(0)
        inq[curNode] = False
        if curNode not in link.keys():
            continue
        for node in link[curNode]:
            if dis[node] > dis[curNode] + link[curNode][node]:
                dis[node] = dis[curNode] + link[curNode][node]
                if inq[node] == True:  #如果在队列中则不管他
                    continue
                inq[node] = True
                queue.append(node)

    return dis


n,m = map(int,input().split())

link = {}
for i in range(m):
    a,b,c = map(int,input().split())
    Lin(a,b,c)
    Lin(b,a,c)


dis = SPFA(1)
#print(parent)
res = max(dis[1:])
if res == float('inf'):
    print(-1)
else:
    print(res)