[NOIP2014]寻找道路

在一个月明星稀的晚上, q0000000 同学被一道绿题切爆了。

这里是题目传送门和千辛万苦后的AC记录

一、 关于思路

求最短路,但是有一些点不能走, q0000000 想先找出这些不能走的点,并把它们标记出来。

要找到“直接或间接与终点连通”的点很不容易,所以考虑建反向边,从终点 \(t\) 出发跑 bfs 或者 dfs 或者 spfa 。这对于时间复杂度影响不大。

这样就找到了从终点直接可达的点,把它们打上标记,比方说 col[u]=1; 。但是还有一些间接可达的——从没被标记过的点出发,找到它们的直接相邻点,也就是 for(int i=h[u];i;i=e[i].nxt)

[NOIP2014]寻找道路

然后就没有问题了,直接跑最短路 (除了floyd)

二、 关于爆零

为什么会爆零呢?

  1. 建图没有必要一正一反,如果为了 bfs 建了反图,那 spfa 就直接从 \(t\) 开始跑呗;
  2. 前后两次打的标记不能覆盖,否则第二次打着打着就发现前面的变化了;
  3. 清空队列, while(!q.empty()) q.pop();
  4. 没有标记 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;
}

THE END

上一篇:P1351 [NOIP2014 提高组] 联合权值


下一篇:蒟蒻们的自闭题单