题目描述
可能有重边
样例
if __name__ == '__main__':
n,m = map(int,input().split(" "))
w = [ [0x3f3f3f3f for i in range(n+1)] for i in range(n+1)]
dist = [0x3f3f3f3f for i in range(n+1)]
vis = [0 for i in range(n+1)]
for i in range(m):
start,end,length = map(int,input().split(" "))
w[start][end] = min(w[start][end],length)
dist[1] = 0
for _ in range(n-1):
t = -1
for i in range(1,n+1):
if not vis[i] and (t ==-1 or dist[i] < dist[t]):
t = i
vis[t] = 1
for i in range(2,n+1):
dist[i] = min(dist[i],dist[t] + w[t][i])
if dist[n] == 0x3f3f3f3f:
print(-1)
else:
print(dist[n])
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla