import heapq
from collections import defaultdict
 
def dijkstra(graph: dict, start: str) -> tuple:
    """Dijkstra法 - O((V+E) log V)
    graph: {u: [(v, weight), ...], ...}
    返り値: (距離辞書, 前任者辞書)
    """
    dist = defaultdict(lambda: float('inf'))
    prev = {}
    dist[start] = 0
 
    # (距離, 頂点) の最小ヒープ
    pq = [(0, start)]
 
    while pq:
        d, u = heapq.heappop(pq)
 
        # 古い情報はスキップ
        if d > dist[u]:
            continue
 
        for v, weight in graph.get(u, []):
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
 
    return dict(dist), prev
 
def reconstruct_path(prev: dict, start: str, end: str) -> list:
    """前任者辞書から経路を復元"""
    path = []
    current = end
    while current != start:
        if current not in prev:
            return []  # 到達不可能
        path.append(current)
        current = prev[current]
    path.append(start)
    return path[::-1]
 
# 使用例
graph = {
    'A': [('B', 2), ('C', 1)],
    'B': [('D', 3)],
    'C': [('E', 4)],
    'E': [('B', 1), ('F', 2)],
    'F': [('D', 1)],
}
dist, prev = dijkstra(graph, 'A')
print(dist)                            # {'A': 0, 'B': 2, 'C': 1, 'D': 5, 'E': 5, 'F': 7}
print(reconstruct_path(prev, 'A', 'D'))  # ['A', 'B', 'D']

def dijkstra_with_visited(graph: dict, start: str) -> dict:
    """visited フラグを使った Dijkstra（ヒープに古いエントリが溜まりにくい）"""
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    visited = set()
    pq = [(0, start)]
 
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
 
        for v, weight in graph.get(u, []):
            if v not in visited:
                new_dist = d + weight
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    heapq.heappush(pq, (new_dist, v))
 
    return dict(dist)

def dijkstra_kth_shortest(graph: dict, start: str, end: str, k: int) -> list:
    """k番目に短い経路の距離を返す
    各頂点に最大 k 回到達するまで探索を続ける
    """
    count = defaultdict(int)  # 各頂点への到達回数
    pq = [(0, start)]
    distances = []
 
    while pq:
        d, u = heapq.heappop(pq)
        count[u] += 1
 
        if u == end:
            distances.append(d)
            if len(distances) == k:
                return distances
 
        if count[u] > k:
            continue
 
        for v, weight in graph.get(u, []):
            heapq.heappush(pq, (d + weight, v))
 
    return distances
 
# 使用例
graph_multi = {
    'A': [('B', 1), ('C', 3)],
    'B': [('C', 1), ('D', 4)],
    'C': [('D', 1)],
    'D': [],
}
print(dijkstra_kth_shortest(graph_multi, 'A', 'D', 3))
# [3, 4, 5]  (A→B→C→D=3, A→C→D=4, A→B→D=5)

def dijkstra_grid(grid: list, start: tuple, end: tuple) -> int:
    """2Dグリッド上の Dijkstra（各セルにコストがある場合）"""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[start[0]][start[1]] = grid[start[0]][start[1]]
 
    pq = [(grid[start[0]][start[1]], start[0], start[1])]
 
    while pq:
        d, r, c = heapq.heappop(pq)
 
        if (r, c) == end:
            return d
 
        if d > dist[r][c]:
            continue
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_dist = d + grid[nr][nc]
                if new_dist < dist[nr][nc]:
                    dist[nr][nc] = new_dist
                    heapq.heappush(pq, (new_dist, nr, nc))
 
    return -1
 
# 各セルの通過コスト
cost_grid = [
    [1, 3, 1, 2],
    [1, 5, 1, 1],
    [4, 2, 1, 3],
    [1, 1, 1, 1],
]
print(dijkstra_grid(cost_grid, (0, 0), (3, 3)))  # 7

def bellman_ford(vertices: list, edges: list, start) -> tuple:
    """Bellman-Ford法 - O(VE)
    edges: [(u, v, weight), ...]
    返り値: (距離辞書, 前任者辞書, 負閉路フラグ)
    """
    dist = {v: float('inf') for v in vertices}
    prev = {v: None for v in vertices}
    dist[start] = 0
 
    # V-1 回の緩和
    for _ in range(len(vertices) - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                updated = True
        if not updated:  # 早期終了
            break
 
    # V 回目：負閉路の検出
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break
 
    return dist, prev, has_negative_cycle
 
# 使用例（負の辺あり）
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', 4), ('A', 'C', 2),
    ('B', 'D', 3), ('C', 'B', -1),
    ('C', 'D', 5), ('D', 'E', 1),
]
dist, prev, neg_cycle = bellman_ford(vertices, edges, 'A')
print(dist)       # {'A': 0, 'B': 1, 'C': 2, 'D': 4, 'E': 5}
print(neg_cycle)  # False
 
# 負閉路の例
edges_neg = [('A', 'B', 1), ('B', 'C', -3), ('C', 'A', 1)]
_, _, neg = bellman_ford(['A','B','C'], edges_neg, 'A')
print(neg)  # True

def bellman_ford_with_negative_cycle_detection(vertices, edges, start):
    """負閉路の影響を受ける全頂点を特定"""
    dist = {v: float('inf') for v in vertices}
    prev = {v: None for v in vertices}
    dist[start] = 0
 
    # V-1 回の緩和
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
 
    # V 回目で更新される頂点 → 負閉路の影響を受ける
    affected = set()
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            affected.add(v)
 
    # 負閉路から到達可能な全頂点も影響を受ける
    # BFS で伝播
    queue = deque(affected)
    while queue:
        node = queue.popleft()
        for u, v, w in edges:
            if u == node and v not in affected:
                affected.add(v)
                queue.append(v)
 
    return dist, affected
 
vertices_nc = ['A', 'B', 'C', 'D', 'E']
edges_nc = [
    ('A', 'B', 1), ('B', 'C', -3), ('C', 'B', 1),  # B-C間に負閉路
    ('C', 'D', 2), ('D', 'E', 1),
]
dist, affected = bellman_ford_with_negative_cycle_detection(vertices_nc, edges_nc, 'A')
print(f"負閉路の影響を受ける頂点: {affected}")
# {'B', 'C', 'D', 'E'} — B,C が負閉路上、D,E は到達可能

from collections import deque
 
def spfa(graph: dict, start) -> tuple:
    """SPFA - Bellman-Ford の改良版
    graph: {u: [(v, weight), ...]}
    平均計算量は Bellman-Ford より大幅に速い
    """
    all_vertices = set(graph.keys())
    for neighbors in graph.values():
        for v, _ in neighbors:
            all_vertices.add(v)
 
    dist = {v: float('inf') for v in all_vertices}
    dist[start] = 0
    in_queue = {v: False for v in all_vertices}
    count = {v: 0 for v in all_vertices}  # 各頂点のキュー入り回数
 
    queue = deque([start])
    in_queue[start] = True
    count[start] = 1
 
    while queue:
        u = queue.popleft()
        in_queue[u] = False
 
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1
                    if count[v] >= len(all_vertices):
                        return dist, True  # 負閉路検出
 
    return dist, False
 
graph_spfa = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 3)],
    'C': [('B', -1), ('D', 5)],
    'D': [('E', 1)],
    'E': [],
}
dist, has_neg = spfa(graph_spfa, 'A')
print(dist)      # {'A': 0, 'B': 1, 'C': 2, 'D': 4, 'E': 5}
print(has_neg)   # False

def floyd_warshall(n: int, edges: list) -> list:
    """Floyd-Warshall法 - O(V³)
    edges: [(u, v, weight), ...]
    返り値: 距離行列
    """
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    # 初期化
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
 
    # DP: 中継点 k を順に追加
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    return dist

def floyd_warshall_with_path(n: int, edges: list) -> tuple:
    """Floyd-Warshall + 経路復元"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
 
    return dist, nxt
 
def get_path(nxt: list, u: int, v: int) -> list:
    """経路復元"""
    if nxt[u][v] is None:
        return []
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path
 
# 使用例
edges = [(0,1,3), (0,3,7), (1,0,8), (1,2,2), (2,0,5), (2,3,1), (3,0,2)]
dist, nxt = floyd_warshall_with_path(4, edges)
print(dist[1][3])           # 3
print(get_path(nxt, 1, 3))  # [1, 2, 3]

def floyd_warshall_with_negative_cycle(n: int, edges: list) -> tuple:
    """Floyd-Warshall + 負閉路検出"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
 
    # 対角成分が負 → 負閉路が存在
    has_negative_cycle = any(dist[i][i] < 0 for i in range(n))
 
    return dist, has_negative_cycle

def transitive_closure(n: int, edges: list) -> list:
    """推移閉包: i から j に到達可能かどうかの行列を求める
    Floyd-Warshall の変形（重みの代わりに到達可能性を管理）
    """
    reach = [[False] * n for _ in range(n)]
 
    for i in range(n):
        reach[i][i] = True
    for u, v in edges:
        reach[u][v] = True
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
 
    return reach
 
edges_reach = [(0, 1), (1, 2), (2, 3)]
reach = transitive_closure(4, edges_reach)
print(reach[0][3])  # True (0→1→2→3)
print(reach[3][0])  # False (3から0へは到達不可)

from collections import defaultdict, deque
 
def dag_shortest_path(graph: dict, start) -> dict:
    """DAG上の最短経路 - O(V + E)"""
    # トポロジカルソート（Kahn）
    in_degree = defaultdict(int)
    all_verts = set(graph.keys())
    for u in graph:
        for v, _ in graph[u]:
            in_degree[v] += 1
            all_verts.add(v)
 
    queue = deque([v for v in all_verts if in_degree[v] == 0])
    topo_order = []
    while queue:
        v = queue.popleft()
        topo_order.append(v)
        for neighbor, _ in graph.get(v, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    # トポロジカル順に緩和
    dist = {v: float('inf') for v in all_verts}
    dist[start] = 0
    for u in topo_order:
        if dist[u] != float('inf'):
            for v, w in graph.get(u, []):
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
 
    return dist
 
dag = {
    'A': [('B', 2), ('C', 6)],
    'B': [('C', 1), ('D', 3)],
    'C': [('D', 1)],
    'D': [],
}
print(dag_shortest_path(dag, 'A'))  # {'A': 0, 'B': 2, 'C': 3, 'D': 4}

def dag_longest_path(graph: dict, start) -> dict:
    """DAG上の最長経路 - O(V + E)
    プロジェクト管理のクリティカルパス分析に使用
    """
    in_degree = defaultdict(int)
    all_verts = set(graph.keys())
    for u in graph:
        for v, _ in graph[u]:
            in_degree[v] += 1
            all_verts.add(v)
 
    queue = deque([v for v in all_verts if in_degree[v] == 0])
    topo_order = []
    while queue:
        v = queue.popleft()
        topo_order.append(v)
        for neighbor, _ in graph.get(v, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    dist = {v: float('-inf') for v in all_verts}
    dist[start] = 0
 
    for u in topo_order:
        if dist[u] != float('-inf'):
            for v, w in graph.get(u, []):
                if dist[u] + w > dist[v]:
                    dist[v] = dist[u] + w
 
    return dist
 
# プロジェクトタスクのDAG（タスク名: [(次タスク, 所要日数)])
project = {
    '設計':     [('開発', 5), ('テスト設計', 3)],
    '開発':     [('テスト', 8)],
    'テスト設計': [('テスト', 2)],
    'テスト':   [('リリース', 3)],
    'リリース': [],
}
longest = dag_longest_path(project, '設計')
print(longest)
# {'設計': 0, '開発': 5, 'テスト設計': 3, 'テスト': 13, 'リリース': 16}
# クリティカルパス: 設計→開発→テスト→リリース = 16日

def johnson(n: int, edges: list) -> list:
    """Johnson法 - O(V² log V + VE)
    edges: [(u, v, weight), ...]
    """
    INF = float('inf')
 
    # Step 1: 仮想頂点 s を追加し、全頂点へ重み 0 の辺を張る
    new_edges = edges + [(n, v, 0) for v in range(n)]
 
    # Step 2: Bellman-Ford で s からの最短距離 h を求める
    h = [INF] * (n + 1)
    h[n] = 0
    for _ in range(n):
        for u, v, w in new_edges:
            if h[u] != INF and h[u] + w < h[v]:
                h[v] = h[u] + w
 
    # 負閉路チェック
    for u, v, w in new_edges:
        if h[u] != INF and h[u] + w < h[v]:
            raise ValueError("負閉路が存在します")
 
    # Step 3: 辺の重みを非負に変換: w'(u,v) = w(u,v) + h[u] - h[v]
    reweighted_graph = defaultdict(list)
    for u, v, w in edges:
        new_w = w + h[u] - h[v]
        reweighted_graph[u].append((v, new_w))
 
    # Step 4: 各頂点から Dijkstra
    dist = [[INF] * n for _ in range(n)]
    for s in range(n):
        d = dijkstra_array(reweighted_graph, s, n)
        for t in range(n):
            if d[t] != INF:
                # 元の重みに戻す
                dist[s][t] = d[t] - h[s] + h[t]
 
    return dist
 
def dijkstra_array(graph, start, n):
    """配列版 Dijkstra（Johnson用）"""
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def astar(graph: dict, start, goal, heuristic) -> tuple:
    """A* 探索
    graph: {u: [(v, weight), ...]}
    heuristic: h(node) → ゴールまでの推定コスト
    返り値: (距離, 経路)
    """
    open_set = [(heuristic(start), 0, start)]  # (f, g, node)
    came_from = {}
    g_score = defaultdict(lambda: float('inf'))
    g_score[start] = 0
    closed = set()
 
    while open_set:
        f, g, current = heapq.heappop(open_set)
 
        if current == goal:
            path = [current]
            while current in came_from:
                current = came_from[current]
                path.append(current)
            return g, path[::-1]
 
        if current in closed:
            continue
        closed.add(current)
 
        for neighbor, weight in graph.get(current, []):
            if neighbor in closed:
                continue
            tentative_g = g + weight
            if tentative_g < g_score[neighbor]:
                g_score[neighbor] = tentative_g
                came_from[neighbor] = current
                f = tentative_g + heuristic(neighbor)
                heapq.heappush(open_set, (f, tentative_g, neighbor))
 
    return float('inf'), []
 
# グリッド上の A* 探索例（マンハッタン距離をヒューリスティックに）
def manhattan_distance(node, goal=(9, 9)):
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
 
# グリッドグラフの構築
def build_grid_graph(rows, cols, blocked=set()):
    graph = {}
    for r in range(rows):
        for c in range(cols):
            if (r, c) in blocked:
                continue
            neighbors = []
            for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in blocked:
                    neighbors.append(((nr, nc), 1))
            graph[(r, c)] = neighbors
    return graph
 
grid_graph = build_grid_graph(10, 10, blocked={(3,3), (3,4), (3,5)})
dist, path = astar(grid_graph, (0, 0), (9, 9), manhattan_distance)
print(f"最短距離: {dist}")  # 18
print(f"経路長: {len(path)}")

def bfs_01(graph: dict, start) -> dict:
    """0-1 BFS - O(V + E)
    graph: {u: [(v, weight), ...]}  weight は 0 or 1
    """
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    dq = deque([start])
 
    while dq:
        u = dq.popleft()
        for v, w in graph.get(u, []):
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                if w == 0:
                    dq.appendleft(v)  # 重み0 → 先頭に追加
                else:
                    dq.append(v)      # 重み1 → 末尾に追加
 
    return dict(dist)

def bidirectional_dijkstra(graph: dict, reverse_graph: dict, start, end) -> int:
    """双方向 Dijkstra
    graph: 順方向の隣接リスト
    reverse_graph: 逆方向の隣接リスト
    """
    INF = float('inf')
 
    dist_f = defaultdict(lambda: INF)
    dist_b = defaultdict(lambda: INF)
    dist_f[start] = 0
    dist_b[end] = 0
 
    pq_f = [(0, start)]
    pq_b = [(0, end)]
 
    visited_f = set()
    visited_b = set()
 
    best = INF
 
    while pq_f or pq_b:
        # 前方から探索
        if pq_f:
            d, u = heapq.heappop(pq_f)
            if d <= best:
                visited_f.add(u)
                for v, w in graph.get(u, []):
                    new_d = d + w
                    if new_d < dist_f[v]:
                        dist_f[v] = new_d
                        heapq.heappush(pq_f, (new_d, v))
                    if v in visited_b:
                        best = min(best, dist_f[v] + dist_b[v])
 
        # 後方から探索
        if pq_b:
            d, u = heapq.heappop(pq_b)
            if d <= best:
                visited_b.add(u)
                for v, w in reverse_graph.get(u, []):
                    new_d = d + w
                    if new_d < dist_b[v]:
                        dist_b[v] = new_d
                        heapq.heappush(pq_b, (new_d, v))
                    if v in visited_f:
                        best = min(best, dist_f[v] + dist_b[v])
 
        # 両方の最小距離が best 以上なら終了
        min_f = pq_f[0][0] if pq_f else INF
        min_b = pq_b[0][0] if pq_b else INF
        if min_f + min_b >= best:
            break
 
    return best

def dial_shortest_path(graph: dict, start, n: int, max_weight: int) -> list:
    """ダイヤル法 - O(V + E + W_max * V)
    辺の重みが [0, max_weight] の非負整数の場合に有効
    """
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
 
    # バケット（循環バッファ）
    num_buckets = max_weight * n + 1
    buckets = [[] for _ in range(num_buckets)]
    buckets[0].append(start)
 
    idx = 0
    found = 0
 
    while found < n:
        while not buckets[idx % num_buckets]:
            idx += 1
 
        u = buckets[idx % num_buckets].pop()
        if dist[u] != idx:
            continue
 
        found += 1
 
        for v, w in graph.get(u, []):
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                buckets[new_dist % num_buckets].append(v)
 
    return dist

# 実際のカーナビでは以下の手法が使われる:
#
# 1. Contraction Hierarchies (CH)
#    - 前処理で重要度の低い頂点を「収縮」し、ショートカット辺を追加
#    - クエリは双方向 Dijkstra で、前処理済みグラフ上で高速に探索
#    - 前処理: O(n log n) 〜 O(n²), クエリ: 数ミリ秒
#
# 2. ALT (A*, Landmarks, Triangle inequality)
#    - ランドマーク頂点への距離を前処理で計算
#    - 三角不等式を使ってヒューリスティックを計算
#    - A* のヒューリスティックとして使用
 
def travel_time_dijkstra(road_network, start, end, departure_time):
    """時間依存の経路検索（ラッシュアワーを考慮）"""
    dist = defaultdict(lambda: float('inf'))
    dist[start] = departure_time
    pq = [(departure_time, start)]
 
    while pq:
        time, u = heapq.heappop(pq)
        if u == end:
            return time - departure_time
        if time > dist[u]:
            continue
        for v, travel_time_func in road_network.get(u, []):
            # travel_time_func(t) は時刻 t における移動時間を返す
            arrival = time + travel_time_func(time)
            if arrival < dist[v]:
                dist[v] = arrival
                heapq.heappush(pq, (arrival, v))
    return float('inf')

def ospf_routing(network: dict, router_id: str) -> dict:
    """OSPF（Open Shortest Path First）のルーティングテーブル計算
    実際の OSPF は Dijkstra 法をベースにしている
    """
    dist, prev = dijkstra(network, router_id)
 
    routing_table = {}
    for dest in dist:
        if dest == router_id:
            continue
        # 次ホップを求める
        next_hop = dest
        while prev.get(next_hop) != router_id:
            next_hop = prev.get(next_hop)
            if next_hop is None:
                break
        routing_table[dest] = {
            'next_hop': next_hop,
            'cost': dist[dest],
            'path': reconstruct_path(prev, router_id, dest),
        }
 
    return routing_table

import math
 
def detect_arbitrage(currencies: list, rates: dict) -> list:
    """為替レートの裁定取引を検出（Bellman-Ford で負閉路を検出）
    rates: {(from, to): rate, ...}
 
    裁定取引: A → B → C → A で利益が出る状態
    rates を -log(rate) に変換すると、負閉路 = 裁定取引機会
    """
    n = len(currencies)
    currency_idx = {c: i for i, c in enumerate(currencies)}
 
    # 辺リストの作成（重み = -log(rate)）
    edges = []
    for (src, dst), rate in rates.items():
        if rate > 0:
            edges.append((currency_idx[src], currency_idx[dst], -math.log(rate)))
 
    # Bellman-Ford
    dist = [float('inf')] * n
    prev = [None] * n
    dist[0] = 0
 
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
 
    # 負閉路の検出
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            # 負閉路を見つけた → 裁定取引が可能
            # サイクルを復元
            cycle = []
            visited = set()
            x = v
            for _ in range(n):
                x = prev[x]
            start = x
            cycle.append(currencies[start])
            x = prev[start]
            while x != start:
                cycle.append(currencies[x])
                x = prev[x]
            cycle.append(currencies[start])
            return cycle[::-1]
 
    return []  # 裁定取引なし
 
currencies = ['USD', 'EUR', 'GBP', 'JPY']
rates = {
    ('USD', 'EUR'): 0.85, ('EUR', 'USD'): 1.20,  # 1.20 > 1/0.85
    ('EUR', 'GBP'): 0.86, ('GBP', 'EUR'): 1.17,
    ('GBP', 'USD'): 1.30, ('USD', 'GBP'): 0.78,
    ('USD', 'JPY'): 110.0, ('JPY', 'USD'): 0.0091,
}
cycle = detect_arbitrage(currencies, rates)
if cycle:
    print(f"裁定取引: {' → '.join(cycle)}")

# BAD: 負辺のあるグラフにDijkstra
graph_neg = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', -3)],   # 負辺!
    'C': [],
}
# Dijkstra は A→C=4 を確定してしまうが、
# 実際は A→B→C = 1+(-3) = -2 が最短
 
# GOOD: Bellman-Ford を使う
vertices = ['A', 'B', 'C']
edges = [('A','B',1), ('A','C',4), ('B','C',-3)]
dist, _, _ = bellman_ford(vertices, edges, 'A')
# dist['C'] = -2 (正しい)

# BAD: V=10000 のグラフに Floyd-Warshall
# → O(V³) = 10^12 回の演算 → 数時間かかる
 
# GOOD: 単一始点なら Dijkstra を使う
# 全点対が本当に必要か再検討する
# 疎グラフなら Johnson のアルゴリズムを検討

# Dijkstra で距離更新時、古いエントリがヒープに残る
# → heappop 時に dist[u] との比較でスキップが必要
 
# BAD: スキップ処理を忘れる
def bad_dijkstra(graph, start):
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        # スキップなし → 古い情報で無駄な処理
        for v, w in graph[u]:
            ...
 
# GOOD: 古いエントリをスキップ
def good_dijkstra(graph, start):
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:  # 古い情報 → スキップ
            continue
        for v, w in graph[u]:
            ...

# BAD: ヒューリスティックが実際のコストを過大評価 → 最適解が保証されない
def bad_heuristic(node, goal):
    # ユークリッド距離 × 2 → 過大評価
    return 2 * math.sqrt((node[0]-goal[0])**2 + (node[1]-goal[1])**2)
 
# GOOD: 許容的なヒューリスティック
def good_heuristic(node, goal):
    # マンハッタン距離（グリッドでは許容的）
    return abs(node[0]-goal[0]) + abs(node[1]-goal[1])

# BAD: 到達不可能な場合のチェックなし
def bad_path_reconstruction(prev, start, end):
    path = [end]
    current = end
    while current != start:
        current = prev[current]  # KeyError の可能性!
        path.append(current)
    return path[::-1]
 
# GOOD: 到達可能性をチェック
def good_path_reconstruction(prev, start, end):
    if end not in prev and end != start:
        return []  # 到達不可能
    path = [end]
    current = end
    while current != start:
        if current not in prev:
            return []
        current = prev[current]
        path.append(current)
    return path[::-1]

# 標準版: O(V²) 空間（k の次元は不要 — 上書きしても正しい）
# 理由: dist[i][k] と dist[k][j] は k 番目の反復で変化しないため
 
# 注意: 経路復元が不要なら dist 行列だけで十分
# 経路復元が必要なら nxt 行列も必要で、合計 O(V²) 空間

# 演習1: 基本実装のテンプレート
class Exercise1:
    """基本的な実装パターンの演習"""
 
    def __init__(self):
        self.data = []
 
    def validate_input(self, value):
        """入力値の検証"""
        if value is None:
            raise ValueError("入力値がNoneです")
        return True
 
    def process(self, value):
        """データ処理のメインロジック"""
        self.validate_input(value)
        self.data.append(value)
        return self.data
 
    def get_results(self):
        """処理結果の取得"""
        return {
            'count': len(self.data),
            'data': self.data
        }
 
# テスト
def test_exercise1():
    ex = Exercise1()
    assert ex.process(1) == [1]
    assert ex.process(2) == [1, 2]
    assert ex.get_results()['count'] == 2
 
    try:
        ex.process(None)
        assert False, "例外が発生するべき"
    except ValueError:
        pass
 
    print("全テスト合格!")
 
test_exercise1()

# 演習2: 応用パターン
from typing import List, Dict, Optional
from datetime import datetime
 
class AdvancedExercise:
    """応用パターンの演習"""
 
    def __init__(self, max_size: int = 100):
        self._items: List[Dict] = []
        self._max_size = max_size
        self._created_at = datetime.now()
 
    def add(self, key: str, value: any) -> bool:
        """アイテムの追加（サイズ制限付き）"""
        if len(self._items) >= self._max_size:
            return False
        self._items.append({
            'key': key,
            'value': value,
            'timestamp': datetime.now().isoformat()
        })
        return True
 
    def find(self, key: str) -> Optional[Dict]:
        """キーによる検索"""
        for item in reversed(self._items):
            if item['key'] == key:
                return item
        return None
 
    def remove(self, key: str) -> bool:
        """キーによる削除"""
        for i, item in enumerate(self._items):
            if item['key'] == key:
                self._items.pop(i)
                return True
        return False
 
    def stats(self) -> Dict:
        """統計情報"""
        return {
            'total_items': len(self._items),
            'max_size': self._max_size,
            'usage_percent': len(self._items) / self._max_size * 100,
            'uptime': str(datetime.now() - self._created_at)
        }
 
# テスト
def test_advanced():
    ex = AdvancedExercise(max_size=3)
    assert ex.add("a", 1) == True
    assert ex.add("b", 2) == True
    assert ex.add("c", 3) == True
    assert ex.add("d", 4) == False  # サイズ制限
    assert ex.find("b")['value'] == 2
    assert ex.remove("b") == True
    assert ex.find("b") is None
    stats = ex.stats()
    assert stats['total_items'] == 2
    print("応用テスト全合格!")
 
test_advanced()

# 演習3: パフォーマンス最適化
import time
from functools import lru_cache
 
# 最適化前（O(n^2)）
def slow_search(data: list, target: int) -> int:
    """非効率な検索"""
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == target:
                return (i, j)
    return (-1, -1)
 
# 最適化後（O(n)）
def fast_search(data: list, target: int) -> tuple:
    """ハッシュマップを使った効率的な検索"""
    seen = {}
    for i, num in enumerate(data):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return (-1, -1)
 
# ベンチマーク
def benchmark():
    import random
    data = list(range(5000))
    random.shuffle(data)
    target = data[100] + data[4000]
 
    start = time.time()
    result1 = slow_search(data, target)
    slow_time = time.time() - start
 
    start = time.time()
    result2 = fast_search(data, target)
    fast_time = time.time() - start
 
    print(f"非効率版: {slow_time:.4f}秒")
    print(f"効率版:   {fast_time:.6f}秒")
    print(f"高速化率: {slow_time/fast_time:.0f}倍")
 
benchmark()