算法
(宽度优先搜索) $O(n+m)$
题意:给你一个无权有向图 $G$,规定一次必须走 3步
,问你最少走多少次才能从点 $S$ 走到点 $T$
分析:
我们只需考虑每次走一步的情况,从点 $S$ 走到点 $V$ 的最短距离 $L$ 对 $3$ 取模有三种可能性,即 $0, 1, 2$(对应于原题中分别表示恰好到达点 $V$,距离点 $V$ 还差一步,距离点 $V$ 还差 $2$ 步)
由于是无权图,所以我们利用 BFS
求出 $S \to T$ 的最短路,再考虑到每次必须走 $3$ 步,所以需对其除以 $3$,如此便可以得到最后的结果
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::queue;
using std::vector;
using P = std::pair<int, int>;
const int INF = 1001001001;
int dist[100005][3];
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
}
int sv, tv;
cin >> sv >> tv;
--sv; --tv;
rep(i, n)rep(j, 3) dist[i][j] = INF;
queue<P> q;
q.emplace(sv, 0);
dist[sv][0] = 0;
while (q.size()) {
auto [v, l] = q.front();
q.pop();
for (int u : to[v]) {
int nl = (l+1) % 3;
if (dist[u][nl] != INF) continue;
dist[u][nl] = dist[v][l] + 1;
q.emplace(u, nl);
}
}
int ans = dist[tv][0];
if (ans == INF) ans = -1;
else ans /= 3;
cout << ans << '\n';
return 0;
}