公式

E - Colorful Route 解説 by cn449 印刷ページ


特殊な最短経路問題です。

概要を述べると、各頂点への経路を最後に使った辺の色ごとに分類し、上位 \(2\) つを管理する BFS により解くことができます。以下、詳細に解説します。

各頂点について、以下の量を管理することにします。ただし、以下、経路においては連続する辺の色が異なるもののみを考えます。

  • \(D_0(v)\) : 頂点 \(v\) までの最短経路長
  • \(C(v)\) : 頂点 \(v\) までに最短の経路で到達するとき、最後に用いられた色として考えられるものの \(1\) つ
  • \(D_1(v)\) : 頂点 \(v\) までの経路のうち、最後に使った辺の色が \(C(v)\) でないものにおける最短経路長

頂点番号、最後に使った辺の色、距離を管理する BFS を行います。具体的な方法の一例を紹介すると、以下のようになります。

現在見ている頂点から出ている各辺について、最後に使った辺の色と異なるのであれば、その辺を利用することができます。行き先の頂点を \(v\) として、\(v\) が未訪問、すなわち \(D_0(v)\) が未計算であれば \(D_0(v), C(v)\) の値を更新し次の状態を queue に入れます。そうではなく、\(D_1(v)\) が未計算かつ \(C(v)\) と現在使おうとしている辺の色が異なるのであれば \(D_1(v)\) の値を更新し次の状態を queue に入れます。このいずれでもなければ、遷移は行いません。

頂点 \(v\) から出る色 \(c\) の辺を使うとき、\(c \neq C(v)\) ならば \(D_0(v)\) に対応する経路、\(c = C(v)\) ならば \(D_1(v)\) に対応する経路を用いることが最適であるため、この BFS の正当性は従います。

各頂点が queue に入る回数は高々 \(2\) 回であり各辺についても処理回数は高々 \(2\) 回であるため、時間計算量は \(O(N + M)\) となります。

実装例

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
const int inf = 1000000010;

int main() {
	int n, m;
	cin >> n >> m;
	vector G(n, vector<pair<int, int>>());
	rep(_, m) {
		int u, v, c;
		cin >> u >> v >> c;
		u--; v--;
		G[u].push_back({ v, c });
	}
	vector<int> d0(n, inf), d1(n, inf), c0(n, -1);
	d0[0] = 0;
	queue<tuple<int, int, int>> Q;
	Q.push({ 0, -1, 0 });
	while (!Q.empty()) {
		auto [v, bad, d] = Q.front(); Q.pop();
		for (auto [u, c] : G[v]) {
			if (c == bad) continue;
			if (d0[u] == inf) {
				d0[u] = d + 1;
				c0[u] = c;
				Q.push({ u, c, d + 1 });
			}
			else if (c != c0[u] && d1[u] == inf) {
				d1[u] = d + 1;
				Q.push({ u, c, d + 1 });
			}
		}
	}
	cout << (d0[n - 1] == inf ? -1 : d0[n - 1]) << '\n';
}

投稿日時:
最終更新: