1865虫洞-最短距離(ベルマンフォード)

1443 ワード
テキストリンク
問題では2つの場所を結ぶ道路が1本より多いかもしれないという.また、これまで問題が戻ってくる必要はなく、あるノードから別のノードへのパスが戻ってくることはありませんでした.この問題では、虫の穴を通って始点を返す問題なので、隣接リストを作成するときに、一方向ではなく双方向を入力します.
adjList[S].append((E,cost))
adjList[E].append((S,cost))
虫穴から他のノードに移動する費用を負の値に格納し、ベルマンフォードを使用します.しかし,出発ノードが特定されていないため,すべてのノードに対してベルマンフォードを実行すればよいと考えられるが,問題は負のループが存在することを確認すれば,どのノードからでも出発できることである.
したがって、最短パスのリストの1番インデックスを0に初期化する必要はなく、現在のノードの値がINF(無限大)であるか否かを決定する条件をベルマンフォードアルゴリズムに加える必要もない.
import sys
input = sys.stdin.readline
 
 
def bellmanFord():
    global isPossible
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for wei, vec in adjList[j]:
                if dist[vec] > wei + dist[j]:
                    dist[vec] = wei + dist[j]
                    if i == N:
                        isPossible = False
                    
 
T = int(input())
 
for _ in range(T):
    N, M, W = map(int, input().split())
 
    INF = 2147483647
    dist = [INF for _ in range(N + 1)]
 
    adjList = [[] for _ in range(N + 1)]
 
    for _ in range(M):
        S, E, T = map(int, input().split())
 
        adjList[S].append((T, E))
        adjList[E].append((T, S))
    
    for _ in range(W):
        S, E, T = map(int, input().split())
 
        adjList[S].append((-T, E))
    
    isPossible = True
    
    bellmanFord()
 
    print("NO" if isPossible else "YES")
コールバック対約束
他の名前によるバラ