グラフの頂点を倍加するタイプの問題ですね。
問題概要
頂点 辺の有向グラフが与えらえます。頂点 から頂点 へと、けんけんぱで移動したいものとします。
1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する」という操作をちょうど 3 回連続で行います。
ちょうどピッタリ で止まるのに必要な操作回数の最小値を求めてください。不可能な場合は -1 を出力してください。
制約
考えたこと
つまり、
- から への路であって、
- 長さが 3 の倍数であるもののうち
- 最短なものを求めよ
という問題であるといえます。「長さが 3 の倍数である」という制約を扱うために、グラフを拡張します。もともとのグラフの
- 頂点 v
を
- (v, 0)
- (v, 1)
- (v, 2)
というふうに拡張します。グラフの頂点数は 3 倍になります。そしてもとのグラフの辺 u -> v については
- (u, 0) -> (v, 1)
- (u, 1) -> (v, 2)
- (u, 2) -> (v, 0)
という風に貼り直します。この新しいグラフ上で (S, 0) -> (T, 0) となるようなパスがあれば、このパスの長さは 3 の倍数であることを保証されます。つまり拡張したグラフにおいて、
(S, 0) から出発して、(T, 0) へと至るまでの最短経路
を BFS で求めればよいです。計算量は となります。
コード
#include <iostream> #include <vector> #include <queue> using namespace std; using Graph = vector<vector<int>>; using pint = pair<int,int>; int N, M; Graph G; int s, t; long long solve() { vector<vector<long long>> dist(N, vector<long long>(3, -1)); dist[s][0] = 0; queue<pint> que; que.push({s, 0}); while (!que.empty()) { pint cur = que.front(); que.pop(); int v = cur.first; int parity = cur.second; for (auto nv : G[v]) { int np = (parity + 1) % 3; if (dist[nv][np] == -1) { dist[nv][np] = dist[v][parity] + 1; que.push({nv, np}); } } } if (dist[t][0] == -1) return -1; else return dist[t][0] / 3; } int main() { cin >> N >> M; G.assign(N, vector<int>()); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; --u, --v; G[u].push_back(v); } cin >> s >> t; --s, --t; cout << solve() << endl; }