AcWing 514. 寻找道路
原题链接
中等
作者:
吴地文笔
,
2020-05-17 15:09:22
,
所有人可见
,
阅读 525
/*
题意:最短路径上每个点的出边指向的点必须能走到终点
方法:SPFA,单源最短路问题(SSSP)
首先,从终点t开始利用反向边图进行dfs1,标出可以经过的点h1[]
其次,从起点s开始利用正向边图进行dfs2(满足h1[]为true),
对于碰到的点y的全部出边点,若都满足h1[]为true,则标出h2[]
最后,通过spfa对h2[]为true的点求从s到t的最短路径即可
*/
#include<bits/stdc++.h>
#define UI unsigned int
using namespace std;
const int N = 10010, M = 200010, INF = 0x3f3f3f3f;
vector<int> a[N], b[N];
queue<int> q;
bool h1[N], h2[N], spfah[N];
int f[N];
void dfs1(int x){ //反向标出h1[]
if(h1[x]) return; //已经标注过,说明存在环,返回
h1[x] = true;
for(UI i = 0; i < b[x].size(); i++){
dfs1(b[x][i]);
}
}
void dfs2(int x){ //正向标出h2[]
if(h2[x]) return; //已经标注过,说明存在环,返回
h2[x] = true;
for(UI i = 0; i < a[x].size(); i++){
int y = a[x][i];
if(!h1[y]) continue; //不满足h1[y]
bool flg = true;
for(UI j = 0; j < a[y].size(); j++){
if(!h1[a[y][j]]){
flg = false;
break;
}
} //只有出边全部h1[]才行
if(flg) dfs2(a[x][i]);
}
}
void spfa(int s, int t){
if(!h2[s]) return; //起点必须有效
f[s] = 0;
spfah[s] = true;
q.push(s);
while(q.size()){
int x = q.front(); q.pop();
for(UI i = 0; i < a[x].size(); i++){
int y = a[x][i];
if(!h2[y]) continue;
if(f[x] + 1 < f[y]){ //更优
f[y] = f[x] + 1;
if(spfah[y]) continue;
q.push(y);
}
}
}
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
while(m--){
int x, y;
scanf("%d %d", &x, &y);
a[x].push_back(y); //正向边
b[y].push_back(x); //反向边
}
int s, t;
scanf("%d %d", &s, &t);
dfs1(t);
dfs2(s);
memset(f, 0x3f, sizeof(f));
spfa(s, t);
if(f[t] == INF) f[t] = -1; //不成立
printf("%d\n", f[t]);
return 0;
}