Portal
Portal1: Luogu
Portal2: LibreOJ
Description
在有向图$\mathrm G$中,每条边的长度均为$1$,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
路径上的所有点的出边所指向的点都直接或间接与终点连通。
在满足条件$1$的情况下使路径最短。
注意:图$\mathrm G$中可能存在重边和自环,题目保证终点没有出边。 请你输出符合条件的路径的长度。
Input
第一行有两个用一个空格隔开的整数$n$和$m$,表示图有$n$个点和$m$条边。
接下来的$m$行每行$2$个整数$x, y$,之间用一个空格隔开,表示有一条边从点$x$指向点$y$。
最后一行有两个用一个空格隔开的整数$s, t$,表示起点为$s$,终点为$t$。
Output
输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。
如果这样的路径不存在,输出$-1$。
Sample Input1
3 2
1 2
2 1
1 3
Sample Output1
-1
Sample Input2
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
Sample Output2
3
Solution
我们先看一个例子:
不妨令起点为$1$,终点为$3$。
这个例子的答案是$3$,路径是$1 \to 4 \to 5 \to 3$。
我们可以先检验出每一个点是否能到终点。可以从终点出发,按照反向边走一遍,然后把走不到的点以及它的入边连的点都删除,像这样:
最后在跑一边$bfs$序,求出最短路就可以了。
Code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 200005;
struct EDGE {
int to, nxt;
} edge1[MAXN], edge2[MAXN];
int n, m, u, v, S, T, cnt1, cnt2, dis[MAXN], head1[MAXN], head2[MAXN];
bool vis[MAXN];
inline void addedge(int u, int v) {//邻接表存图
edge1[++cnt1].to = v; edge1[cnt1].nxt = head1[u]; head1[u] = cnt1;
edge2[++cnt2].to = u; edge2[cnt2].nxt = head2[v]; head2[v] = cnt2;//反向边
}
inline void bfs1(int cur) {
queue<int> Q;
Q.push(cur);
vis[cur] = 1;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = head2[u]; ~i; i = edge2[i].nxt) {//遍历每一个点
int v = edge2[i].to;
if (!vis[v]) {
vis[v] = 1;
Q.push(v);
}
}
}
}
inline bool check(int u) {//判断是否能到达终点
for (int i = head1[u]; ~i; i = edge1[i].nxt)
if (!vis[edge1[i].to]) return 0;
return 1;
}
inline bool bfs2(int cur) {
queue<int> Q;
Q.push(cur);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
if (!check(u)) continue;
for (int i = head1[u]; ~i; i = edge1[i].nxt) {//遍历每一个点
int v = edge1[i].to;
if (dis[v] == -1) {
dis[v] = dis[u] + 1;
Q.push(v);
if (v == T) {
printf("%d\n", dis[T] + 1);
return 1;
}
}
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
memset(head1, -1, sizeof(head1));
memset(head2, -1, sizeof(head2));
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
addedge(u, v);//加边
}
scanf("%d%d", &S, &T);
bfs1(T);//求出终点能到的点
memset(dis, -1, sizeof(dis));
if (!bfs2(S)) printf("-1\n");
return 0;
}
Attachment
Article Author: XiaoHuang