AOJ 1358 Sibling Rivalry
解法
終点から更新していくベルマンフォードのように解いた.
まず,各頂点から a, b, c で行ける頂点を予め求めておく.
d[v] := その頂点から終点に必ずたどり着けるなら,その時の最小値
とする.d[n-1] = 0 とする.
すると,d[v] は v から a, b, c それぞれで行ける頂点集合を Va, Vb, Vc とおけば,d[v] = max( min( d[Va] ), min( d[Vb] ), min( d[Vc] ) ) となることがわかる.
あとは,ベルマンフォードの要領で,更新が終わるまで続けるとよい.
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int INF = 1e9; int main() { int n, m; vector<int> a(3); cin >> n >> m >> a[0] >> a[1] >> a[2]; vector<vector<int>> g(n); for(int i=0; i<m; ++i) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); } vector<vector<vector<int>>> to(n, vector<vector<int>>(3)); for(int v = 0; v < n; ++v) { vector<vector<bool>> visited(101, vector<bool>(n)); visited[0][v] = true; for(int i = 0; i < 100; ++i) { for(int j = 0; j < n; ++j) { if(visited[i][j]) { for(auto t : g[j]) { visited[i+1][t] = true; } } } } for(int i = 0; i < 3; ++i) { for(int j = 0; j < n; ++j) { if(visited[a[i]][j]) { to[v][i].push_back(j); } } } } vector<int> d(n, INF); d[n-1] = 0; while(true) { bool update = false; for(int v = 0; v < n; ++v) { vector<int> mi(3, INF); for(int j = 0; j < 3; ++j) { for(auto t : to[v][j]) { mi[j] = min(mi[j], d[t]); } } int ma = *max_element(mi.begin(), mi.end()) + 1; if(ma < d[v]) { update = true; d[v] = ma; } } if(!update) { break; } } if(d[0] == INF) { cout << "IMPOSSIBLE" << endl; } else { cout << d[0] << endl; } }