Day 006-Q5 — Phase 4 総復習

2026-04-19 水色 / Phase 4 ★★★★☆ ベルマンフォード + BIT

問題

$N$ 頂点 $M$ 辺の重み付き有向グラフが与えられます。

  1. 頂点 1 から頂点 $N$ への最短距離を求めてください（到達不能なら -1）
  2. グラフに負の閉路が存在するか判定してください
  3. クエリ $Q$ 個に対して、配列 $A$ の A[l]+...+A[r] を BIT で出力

制約

$2 \le N \le 500$
$1 \le M \le 5000$
$-10^4 \le w_i \le 10^4$
$1 \le K \le 10^5$
$1 \le Q \le 10^5$

入出力例

入力例 1

4 5
1 2 3
1 3 1
3 2 -2
2 4 2
3 4 5
5
1 2 3 4 5
3
1 3
2 4
1 5

出力例 1

2
No
6
9
15

ヒント (段階的開示)

ヒント1: 方向性
3つの独立した処理を組み合わせた総復習問題。
ヒント2: アプローチ
最短距離: ベルマンフォード法（負辺あり）
負の閉路: $N$ 回目も緩和できれば閉路あり
区間和: BIT（Fenwick Tree）
ヒント3: 誘導 
for i in range(N):
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if i == N - 1:
                negative_cycle = True

模範解答 (Python)

import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def query(self, l, r):
        return self.sum(r) - self.sum(l - 1)

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))

    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    negative_cycle = False

    for i in range(N):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if i == N - 1:
                    negative_cycle = True

    if negative_cycle:
        print(-1)
    else:
        print(dist[N] if dist[N] != INF else -1)

    print("Yes" if negative_cycle else "No")

    K = int(input())
    A = list(map(int, input().split()))
    bit = BIT(K)
    for i, a in enumerate(A):
        bit.add(i + 1, a)

    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(bit.query(l, r))

main()

Step-by-Step 解説

1ベルマンフォード法
$N-1$ 回の緩和で最短経路が確定。$N$ 回目に更新が発生 = 負の閉路が存在。
2負の閉路の検出
0-indexed で i == N-1 が $N$ 回目の更新に対応。
3BIT での区間和
初期配列を全て add() で登録後、sum(r) - sum(l-1) でクエリに答える。

よくあるミス

ミス原因正しい書き方
dist[u] != INF のチェックを忘れるINF + w で誤更新必ずチェックする
$N$ 回目の判定間違い0-indexed と 1-indexed の混乱for i in range(N) で i == N-1 が $N$ 回目
BIT の初期化を忘れる全要素 0 のままクエリ全要素を add() で追加

次のステップ

  • Phase 5 へ: 遅延伝播セグメント木・最小全域木（Kruskal）

自己評価

自分の回答

気づき・メモ