题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Python 代码

import sys
import collections
N = 510
M = 100010
def bellmanford():
    for i in range(k):
        backup = dist.copy() 
        for j in range(m):
            a = edge[j][0]
            b = edge[j][1]
            wab = edge[j][2]
            dist[b] = min(dist[b], backup[a] + wab)

    if dist[n] > sys.maxsize/2.0 :return -1
    return dist[n]

if __name__ == "__main__":
    dist = [sys.maxsize]*N
    dist[1] = 0
    backup = [sys.maxsize]*N
    edge = collections.defaultdict(list)
    n,m,k = map(int, input().split())

    for i in range(m):
        a,b,wei = map(int, input().split())
        edge[i].append(a)
        edge[i].append(b)
        edge[i].append(wei)

    t = bellmanford()
    if t == -1:
        print("impossible")
    else:
        print(t)

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla