在一个月明星稀的晚上, q0000000 同学被一道绿题切爆了。
一、 关于思路
求最短路,但是有一些点不能走, q0000000 想先找出这些不能走的点,并把它们标记出来。
要找到“直接或间接与终点连通”的点很不容易,所以考虑建反向边,从终点 \(t\) 出发跑 bfs 或者 dfs 或者 spfa 。这对于时间复杂度影响不大。
这样就找到了从终点直接可达的点,把它们打上标记,比方说 col[u]=1;
。但是还有一些间接可达的——从没被标记过的点出发,找到它们的直接相邻点,也就是 for(int i=h[u];i;i=e[i].nxt)
。
然后就没有问题了,直接跑最短路 (除了floyd) 。
二、 关于爆零
为什么会爆零呢?
- 建图没有必要一正一反,如果为了 bfs 建了反图,那 spfa 就直接从 \(t\) 开始跑呗;
- 前后两次打的标记不能覆盖,否则第二次打着打着就发现前面的变化了;
- 清空队列,
while(!q.empty()) q.pop();
; - 没有标记 1 或有标记 2 的点都是不能走的。
三、 关于代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+10;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
struct edge{int v,nxt;}e[M];
int n,m,s,t,dis[N],tot,h[N];
bool vis[N],col1[N],col2[N];
queue<int> q;
inline void add(int u,int v){
e[++tot]=(edge){v,h[u]};
h[u]=tot;
}
inline void bfs(){
memset(vis,0,sizeof(vis));
dis[t]=0;
q.push(t);
vis[t]=1;
while(!q.empty()){
int u=q.front();q.pop();
col1[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
inline void spfa(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
dis[t]=0;
q.push(t);
vis[t]=1;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!col1[v]||col2[v]) continue;
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
add(v,u);
}
scanf("%d%d",&s,&t);
bfs();
for(int u=1;u<=n;++u){
if(col1[u]) continue;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
col2[v]=1;
}
}
spfa();
if(dis[s]==INF) puts("-1");
else printf("%d\n",dis[s]);
return 0;
}