Pythonでロードトリップの国境越え最小回数と総移動コストを求めるプログラム

問題の概要

複数の国にまたがるさまざまな都市を訪れるロードトリップを計画することを考えます。道路のリスト「R」が与えられ、各要素は (x, y, cost) という形式で表されます。x は道路の起点となる都市、y は行き先の都市、cost はその道路を通行するときにかかるコストです。さらに、各国ごとの都市リストを要素とするリスト「C」も与えられます。出発都市 s と目的地 e が指定され、s から e へ移動したいとします。このとき、旅を完了するために必要な「国境をまたぐ移動の最小回数」と「移動にかかる総コスト」を求め、この2つの値を出力します。

例として、入力が R = [[0, 1, 2], [1, 2, 2], [0, 2, 3], [1, 3, 3]]、C = [[0], [1], [2, 3]]、s = 0、e = 3 の場合、出力は (2, 5) になります。

0 から 3 へ向かうには、0 → 1 → 3 という経路を選びます。この経路で使用する道路は [0, 1, 2] と [1, 3, 3] であり、国境をまたぐ移動は合計2回、総コストは 2 + 3 = 5 となります。

解き方のアプローチ

この問題は、ダイクストラ法（Dijkstra's algorithm）を少し工夫して適用することで解けます。鍵となるアイデアは、「国境を越える道路」のコストに非常に大きな定数（ここでは 10¹⁰）をあらかじめ加算しておくことです。これにより、最短経路の探索では「国境越えの回数」が最優先で最小化され、同一回数の中では実際の移動コストが最小になる経路が自動的に選ばれます。最終的な距離値を 10¹⁰ で割ると、商が国境越えの回数、余りが総コストに対応します。

具体的な手順は次のとおりです。

• cont := デフォルト値が 0 の新しいマップ（辞書）を用意する
• C の各インデックス idx と各要素 item に対して、item に含まれるすべての都市 k について cont[k] := idx を設定する（＝各都市が属する国を記録する）
• adj_list := 値としてリストを持つ新しいマップ（隣接リスト）を用意する
• R の各要素 a, b, wt について次を行う：
  • cont[a] と cont[b] が異なる場合（＝国境を越える道路の場合）、wt := wt + 10¹⁰ とする
  • adj_list[a] の末尾にペア (b, wt) を追加する
• distance := デフォルト値が 10²⁰ の新しいマップを用意する
• distance[s] := 0 を設定する
• visited := 新しいセット（訪問済みノードの管理用）を用意する
• t := ペア (0, s) を格納した新しいヒープを用意する
• t が空になるまで、次の手順を繰り返す：
  • (d, c) := ヒープから最小の要素を取り出す
  • c がすでに visited に含まれている場合は、次の反復へスキップする
  • c を visited に追加する
  • adj_list[c] の各要素 j, wt について、distance[j] > d + wt が成り立つなら、distance[j] := d + wt と更新し、ペア (d + wt, j) をヒープ t に挿入する
• (distance[e] ÷ 10¹⁰ の商, distance[e] mod 10¹⁰) のペアを返す

このアルゴリズムの計算量は、通常のダイクストラ法と同じく O((V + E) log V) であり、都市数や道路数が増えても効率的に動作します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from collections import defaultdict
from heapq import heappush, heappop

def solve(R, C, s, e):
    cont = defaultdict(int)
    for idx, item in enumerate(C):
        for k in item:
            cont[k] = idx

    adj_list = defaultdict(list)
    for a, b, wt in R:
        if cont[a] != cont[b]:
            wt += 10 ** 10
        adj_list[a].append((b, wt))

    distance = defaultdict(lambda: 10 ** 20)
    distance[s] = 0
    visited = set()

    t = [(0, s)]
    while t:
        d, c = heappop(t)
        if c in visited:
            continue
        visited.add(c)
        for j, wt in adj_list[c]:
            if distance[j] > d + wt:
                distance[j] = d + wt
                heappush(t, (d + wt, j))

    return distance[e] // 10 ** 10, distance[e] % 10 ** 10

print(solve([[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3))

入力

[[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3

出力

(2, 5)