[洛谷]P2296 寻找道路 (#最短路)

题目描述

在有向图 GG 中，每条边的长度均为 11，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
2. 在满足条件11的情况下使路径最短。

注意：图 GG 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

输入格式

第一行有两个用一个空格隔开的整数 nn 和 mm，表示图有 nn 个点和 mm 条边。

接下来的 mm 行每行 22 个整数 x,yx,y，之间用一个空格隔开，表示有一条边从点 xx 指向点yy。

最后一行有两个用一个空格隔开的整数 s, ts,t，表示起点为 ss，终点为 tt。

输出格式

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1−1。

输入输出样例

输入 #1复制

3 2  
1 2  
2 1  
1 3  

输出 #1复制

-1

输入 #2复制

6 6  
1 2  
1 3  
2 6  
2 5  
4 5  
3 4  
1 5  

输出 #2复制

3

说明/提示

解释1：

如上图所示，箭头表示有向道路，圆点表示城市。起点11与终点33不连通，所以满足题目描述的路径不存在，故输出-1−1 。

解释2：

如上图所示，满足条件的路径为11- >33- >44- >55。注意点22 不能在答案路径中，因为点22连了一条边到点66，而点66 不与终点55 连通。

【数据范围】

对于30\%30%的数据，0 < n \le 100<n≤10，0 < m \le 200<m≤20;

对于60\%60%的数据，0 < n \le 1000<n≤100，0 < m \le 20000<m≤2000;

对于100\%100%的数据，0 < n \le 10000, 0 < m \le 200000,0 < x,y,s,t \le n, x,s \ne t0<n≤10000,0<m≤200000,0<x,y,s,t≤n,x,s≠t。

---

思路

Noip系列中最恶臭的题目......虽然难度只是绿，可是把我折腾了2个小时......

实际上本题只比单源最短路径多了一个要求。然而，语文不好的同学一定会死在那句话上：比如我

路径上的所有点的出边所指向的点都直接或间接与终点连通。

我刚看这句话，缓缓地打出了一个问号。。10 years later，我大概明白了是什么意思：求从起点到终点的一条最短路，使其上任一点所有子节点都能到达终点。

因此，本题仍然让我们求单源最短路径，考虑使用dijkstra。显然有这样一个思路，求最短路然后保证路径上任一点所有子节点都能到达终点。不妨先标记再求最短路：

1. 标记能出现在路径上的点。

2. 对于已经标记的点跑一遍dijkstra。

复杂度可能较大，我一开始打了个20分的dfs+dijkstra。T的满天飞。

显然，求最短路地球人都会，主要问题是如何标记。先放代码：

#include <stdio.h>
#include <iostream>
#include <queue>
#include <memory.h>
#define inf 2e9+7
#define N 10001
#define M 200001
using namespace std;
int n,m,head[N][2]/*head[u][0]:起点->终点；head[u][1]:终点->起点*/,cnt,s,dis[N]/*单源最短路*/,t;
bool vis[N],check[N]/*标记点*/;
struct edge//链式前向星 
{
	int nxt,to,val;
}e[M<<1],ae[M<<1];
struct node//优先队列优化dijkstra 
{
	int w,now;
	inline bool operator <(const node &x)const
	{
		return w>x.w;
	}
};
priority_queue<node> q;
queue<int> q1;//标记每个点能否到达终点t 
inline void add(int u,int v)
{
	e[++cnt].to=v;//构建原图 
	e[cnt].val=1;
	e[cnt].nxt=head[u][0];
	head[u][0]=cnt;
	swap(u,v);
	ae[cnt].to=v;//反向建图 
	ae[cnt].val=1;
	ae[cnt].nxt=head[u][1];
	head[u][1]=cnt;
}
inline void bfs_if_reachable(int start)//搜索从终点t到达的点（反向建图） 
{
	check[start]=1;
	q1.push(start);
	register int i;
	while(!q1.empty())
	{
		int u(q1.front());
		q1.pop();
		for(i=head[u][1];i;i=ae[i].nxt)//遍历反向图，开始为终点t 
		{
			int v(ae[i].to);
			if(check[v]==0)//没哟编辑就则标记加入队列 
			{
				check[v]=1;
				q1.push(v);
			}
		}
	}
}
int mark[N]; 
void bfs()//从起点s遍历标记可以选中的点 
{
	register int i,j;
	for(i=1;i<=n;i++)
	{
		if(check[i])//首先要求该点必须能到终点t 
		{
			mark[i]=1; 
			for(j=head[i][0];j;j=e[j].nxt)//判断子节点是否能到达终点t 
			{
				int v(e[j].to);
				if(check[v]==0)
				{
					mark[i]=0;
					break;
				}
			}
		}
	}
}
inline void dijkstra()
{
	register int i;
	for(i=1;i<=n;i++)
	{
		dis[i]=inf;
		vis[i]=0;
	}
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty())
	{
		node x(q.top());
		q.pop();
		int u(x.now);
		if(vis[u]) continue;
		vis[u]=1;
		for(i=head[u][0];i;i=e[i].nxt)//这个在原图和反向图遍历都可以 
		{
			int v(e[i].to);
			if(!mark[v]) continue;//必须是标记的点 
			if(dis[v]>dis[u]+e[i].val)
			{
				dis[v]=dis[u]+e[i].val;
				q.push((node){dis[v],v});
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register int i,j,k;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		if(u==v) continue;//判断重边 
		add(u,v);
	}
	cin>>s>>t;//s起点，t终点 
	bfs_if_reachable(t);//第1次标记每个点是否能到达终点t 
	if(check[s]==0)//起点不能就-1 
	{
		cout<<-1<<endl;
		return 0;
	}
	bfs();//第2次标记每个点的子节点能否到达终点，也就是每个点能不能出现在路径中 
	dijkstra();//求最短路 
	//for(i=1;i<=n;i++)
	//{
	//	cout<<dis[i]<<' ';
	//}cout<<endl;
	if(dis[t]>=inf)
	{
		cout<<-1<<endl;
		return 0;
	}
	cout<<dis[t]<<endl;
	return 0;
}

从终点往前bfs，这样可以知道哪些点可以到终点。如果硬是正向搜都跑n次，而反向搜只需要跑1次。