Official
E - Colorful Route Editorial
by
E - Colorful Route Editorial
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';
}