問題
$N$ 頂点の無向グラフ（初期辺なし）に対し、以下のクエリを $Q$ 個処理せよ：
add u v w: 辺 $(u, v)$ を重み $w$ で追加する。del u v: 辺 $(u, v)$ を削除する（必ず存在する辺）。query s t: 頂点 $s$ から $t$ への最短距離を出力する（到達不可なら -1）。
全クエリをオフラインで先読み可能。各辺の追加・削除は対になっている。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 500$ |
| $Q$ | $1 \le Q \le 10^4$ |
| $w$（辺重み） | $1 \le w \le 10^9$ |
| 形式 | add/del は対、オフライン処理可 |
入出力例
入力例 1
4 6
add 1 2 3
add 2 3 2
query 1 3
del 2 3
add 3 4 1
query 1 4出力例 1
5
-1概念図: セグメント木上の分割統治
ヒント（段階的開示）
ヒント1: 方向性
全クエリをオフラインで先読みして各辺の存在区間 $[l, r)$ を求め、区間セグメント木に登録する。DFS で葉に到達したとき（= ある時刻）に query クエリに回答する。
ヒント2: アプローチ
- add/del を対応付けて辺の存在区間を計算
- クエリ時刻軸上のセグメント木に辺を登録（$O(\log Q)$ ノード/辺）
- セグメント木を DFS し、各ノードで辺を Floyd-Warshall に統合
- 葉ノードで query に回答
- 状態はディープコピーで伝播（Undo 不要）
ヒント3: Floyd-Warshall 辺追加
def add_edge_warshall(dist, N, u, v, w):
"""辺(u,v,w)を距離行列に追加してWarshall更新"""
for i in range(N):
for j in range(N):
d1 = dist[i][u] + w + dist[v][j]
if d1 < dist[i][j]:
dist[i][j] = d1
d2 = dist[i][v] + w + dist[u][j]
if d2 < dist[i][j]:
dist[i][j] = d2模範解答 (Python)
import sys
from copy import deepcopy
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
queries_raw = [input().split() for _ in range(Q)]
INF = float('inf')
active = {}
edge_intervals = []
query_at = {}
for i, qr in enumerate(queries_raw):
if qr[0] == 'add':
u, v, w = int(qr[1])-1, int(qr[2])-1, int(qr[3])
key = (min(u,v), max(u,v))
active[key] = (w, i)
elif qr[0] == 'del':
u, v = int(qr[1])-1, int(qr[2])-1
key = (min(u,v), max(u,v))
w, st = active.pop(key)
edge_intervals.append((key[0], key[1], w, st, i))
else:
s, t = int(qr[1])-1, int(qr[2])-1
query_at[i] = (s, t)
for (u, v), (w, st) in active.items():
edge_intervals.append((u, v, w, st, Q))
seg = [[] for _ in range(4 * Q + 4)]
def seg_add(node, nl, nr, l, r, edge):
if r <= nl or nr <= l: return
if l <= nl and nr <= r:
seg[node].append(edge); return
mid = (nl + nr) // 2
seg_add(2*node, nl, mid, l, r, edge)
seg_add(2*node+1, mid, nr, l, r, edge)
for u, v, w, l, r in edge_intervals:
seg_add(1, 0, Q, l, r, (u, v, w))
init_dist = [[INF]*N for _ in range(N)]
for i in range(N): init_dist[i][i] = 0
answers = {}
def dfs(node, nl, nr, dist):
nd = deepcopy(dist)
for u, v, w in seg[node]:
for i in range(N):
for j in range(N):
if nd[i][u] + w + nd[v][j] < nd[i][j]:
nd[i][j] = nd[i][u] + w + nd[v][j]
if nd[i][v] + w + nd[u][j] < nd[i][j]:
nd[i][j] = nd[i][v] + w + nd[u][j]
if nl + 1 == nr:
if nl in query_at:
s, t = query_at[nl]
answers[nl] = nd[s][t] if nd[s][t] < INF else -1
else:
mid = (nl + nr) // 2
dfs(2*node, nl, mid, nd)
dfs(2*node+1, mid, nr, nd)
sys.setrecursionlimit(300000)
dfs(1, 0, Q, init_dist)
out = [str(answers[i]) for i, qr in enumerate(queries_raw) if qr[0] == 'query']
print('\n'.join(out))
solve()Step-by-Step 解説
Step 1: 辺の存在区間の算出
add と del を対応付けて、辺の存在区間 $[t_{add}, t_{del})$ を求める。最後まで残る辺は $[t_{add}, Q)$。
Step 2: セグメント木への区間登録
クエリ時刻軸 $[0, Q)$ をセグメント木で管理。各辺をその存在区間に対応する $O(\log Q)$ ノードに登録。
Step 3: DFS + Floyd-Warshall
セグメント木を DFS。各ノードで登録辺を距離行列に追加（Warshall 更新）し、ディープコピーで子ノードに伝播。葉で query に回答。
Step 4: 計算量
| 処理 | 計算量 |
|---|---|
| 区間登録 | $O(Q \log Q)$ |
| 各ノードの Warshall 更新 | $O(N^2)$/辺 × $O(Q \log Q)$ 辺 |
| deepcopy | $O(N^2 \log Q)$ 回 |
| 全体 | $O(N^2 Q \log Q)$（$N \le 500$） |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 辺の存在区間の境界ずれ | $[l, r)$ の半開区間を誤認識 | del 時刻を $r$、add 時刻を $l$ として $[l, r)$ で登録 |
| 無向辺の対称性を忘れる | 一方向のみ Warshall 更新 | 必ず両方向（$i \to u + v \to j$ と $i \to v + u \to j$）を更新 |
| deepcopy のコスト | $N=500$ でディープコピーが遅い | numpy 配列や C 拡張で高速化、またはオフライン整理で事前削減 |
次のステップ
発展問題: $N \le 10^5$ の動的グラフで辺追加のみの SSSP（Offline Incremental SSSP）。ヒント: 辺追加の単調性 + Offline LCT（辺が MST に追加されたとき距離が変化）を組み合わせて $O((N+Q) \log N)$ で解け。