各都市から周回旅行(往復)が可能かどうかを判定するC++プログラム

問題の概要

n個の都市と、それらを結ぶm本の道路があるとします。各道路は一方通行であり、出発都市から目的地の都市まで移動するには一定の時間がかかります。道路の情報は配列 roads として与えられ、各要素は (出発地, 目的地, 時間) という形式で表されます。

ここで、ある人物がある都市を出発し、1本以上の道路を通って再び出発した都市へ戻ってくる旅を「周回旅行(ラウンドトリップ)」と定義します。各都市について、その都市を起点とした周回旅行が可能かどうかを判定してください。可能であれば周回に必要な時間を出力し、不可能な場合は -1 を出力します。

たとえば、入力が n = 4、m = 4、roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}} の場合、出力は 26 26 26 26 となります。このグラフではすべての都市が1つの閉路でつながっているため、どの都市から出発しても周回にかかる時間は 26 になります。

解法のアプローチ

この問題は、各都市を起点として優先度付きキュー(ヒープ)を使ったダイクストラ法風の探索を行うことで解けます。各都市 i について、出発時に距離 0 を設定してグラフを探索し、探索中に再び出発都市 i に到達した時点で、その累積時間が周回旅行に必要な時間となります。キューが空になっても出発都市へ戻れなかった場合は、その都市からの周回は不可能であるため -1 を出力します。

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

ペアを要素に持つ2次元配列 graph(n) を定義する
i := 0 から i < m の間、i を 1 ずつ増やしながら繰り返す:
    x := roads[i] の1番目の値
    y := roads[i] の2番目の値
    z := roads[i] の3番目の値
    x と y をそれぞれ 1 減らす
    ペア (y, z) を graph[x] の末尾に追加する
i := 0 から i < n の間、i を 1 ずつ増やしながら繰り返す:
    q := 新しい優先度付きキュー
    配列 dst を定義する
    ペア (0, i) を q に挿入する
    q が空でない間、次を繰り返す:
        p := q の先頭要素
        q から先頭要素を取り除く
        dt := p の1番目の値
        curr := p の2番目の値
        もし dst[curr] が 0 と等しいなら:
            dst[curr] := dt
            ループを抜ける
        もし dst[curr] が -1 と等しくないなら:
            以降をスキップして次の反復へ
        dst[curr] := dt
        graph[curr] の各要素 next について:
            tp := next の1番目の値
            cst := next の2番目の値
            ペア (dt + cst, tp) を q に挿入する
    もし dst[i] が 0 と等しいなら:
        dst[i] := -1
    dst[i] を出力する

実装例

理解を深めるために、以下のC++による実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int modval = (int) 1e9 + 7;
#define N 100
void solve(int n, int m, vector<tuple<int, int, int>> roads ) {
    vector<vector<pair<int, int>>> graph(n);
    for(int i = 0; i < m; i++) {
        int x, y, z;
        tie(x, y, z) = roads[i];
        x--; y--;
        graph[x].emplace_back(y, z);
    }
    for(int i = 0; i < n; i++) {
        priority_queue<pair<int, int>> q;
        vector<int> dst(n, -1);
        q.emplace(0, i);
        while(q.size()){
            pair<int, int> p = q.top();
            q.pop();
            int curr, dt;
            tie(dt, curr) = p;
            if(dst[curr] == 0) {
                dst[curr] = dt;
                break;
            }
            if(dst[curr] != -1)
                continue;
            dst[curr] = dt;
            for(auto next : graph[curr]){
                int tp, cst;
                tie(tp, cst) = next;
                q.emplace(dt + cst, tp);
            }
        }
        if(dst[i] == 0)
            dst[i] = -1;
        cout<< dst[i]<< endl;
    }
}
int main() {
    int n = 4, m = 4;
    vector<tuple<int, int, int>> roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}};
    solve(n, m, roads);
    return 0;
}

入力

4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}

出力

26
26
26
26

まとめ

このプログラムでは、各都市を起点に優先度付きキューを用いた探索を実行し、出発都市へ戻ってきた時点の累積コストを周回時間として記録します。距離配列 dst を -1 で初期化し、出発都市自身の距離が 0 のまま残っていれば周回不可能と判断して -1 を出力する仕組みです。すべての都市についてこの処理を繰り返すことで、各都市からの周回旅行の可否と所要時間を判定できます。都市数を V、道路数を E とすると、計算量は全体で O(V・(V + E) log V) 程度となります。