【题解】Blocked Roads

题目：Blocked Roads

题意：

给定n个点和m条边，对于每条边有一个询问：如果删除该边是否存在一条路径使得从1到n的距离最短？

思路：

• 思路很简单，bfs找最短路径。 看到最短路径题先bfs一下
• 第一个问题：怎么知道我们删除的是第几条边呢？用vector<pair<int,int>>预存每条边，然后在bfs时判断一下。
• 第二个问题：1. 如果对于每个询问我们都从头开始bfs，是否会超时？2. 如何优化？ 1. 实践证明无脑bfs 会Time Limit. 2. 我们可以提前bfs一次并预存一条最短路径，在询问时如果我们发现这条边在最短路径中出现过，那么我们就直接输出最短路径长度，否则我们就bfs一次看是否能够达到n。
• 第三个问题：1. 怎么求最短路径长度？ 2. 怎么存最短路径？1. 我们可以用len数组表示走到第i个点时路径长度。在第一次bfs时，len[终点]=min(len[终点]，len[起点]+1)。2. 我们可以用path数组表示走到第i个点前一个点。换句话说就是path中下标是边的终点，存的值是边的起点。可能有读者会问：为什么不用下标存起点，值存终点呢？好问题， 注意我们的bfs终止的条件是队列中某个点等于n，return的位置提前于下面的if判断，如果从起点开始存我们将存不到终点。

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<set>
#include<map>

using namespace std;
const int N = 2e5 + 10,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
typedef long long ll;

int n, m;
vector<PII>p;//记录边的编号
vector<int>T[N];//t[i]={}，括号内表示所有以i起点且与i直接相连的点
int len[N];//len[i]表示从1走到i的最短距离
int path[N];//path数组存最短路径，path[i]表示走到i前的那个点，例如最短路中有一点边是2->5，那么path[5]=2

int bfs(int u)
{
	memset(len, 0x3f, sizeof(len));
	len[1] = 0;
	queue<int>q;
	q.push(1);
	
	while (!q.empty())
	{
		int t = q.front(); q.pop();
		if (t == n)return len[n];//已经找到终点

		for (int i = 0; i < T[t].size(); ++i)
		{
			if (t == p[u].first && T[t][i] == p[u].second) continue;//删除第u条边
			
			if (len[T[t][i]] > len[t] + 1)//防止反复遍历。例如:如果有边[1,5]，那么就没有必要再走[1,2],[2,4],[4,5]
			{
				q.push(T[t][i]);
				len[T[t][i]] = len[t] + 1;
				//最短路可能不止一条边，所以可能会产生覆盖，但是这不重要，我们只要记录一条最短边就可以了
				if(u==0)path[T[t][i]] = t;
			}
		}
	}

	return -1;//走不到n返回-1
}

int main()
{
	cin >> n >> m;

	p.push_back({ 0,0 });
	for (int i = 1; i <= m; ++i)
	{
		int x, y;
		cin >> x >> y;
		p.push_back({ x,y });
		T[x].push_back(y);
	}
	
	int res=bfs(0);//在不删除点的情况下找到最短路长度

	if (res == -1)//如果无法走到n
	{
		for (int i = 0; i < m; ++i)cout << res << endl;
		return 0;
	}

	//汇总记录最短路的各个边到set中，方便在询问时快速得到所删除边是否在最短路中出现
	set<PII>w;
	int l=n;
	while (l!=1)
	{
		if (path[l] == 0)break;
		PII a = {path[l],l};
		w.insert(a);
		l = path[l];
	}

	for (int i = 1; i <= m; ++i)
	{
		if (w.count(p[i])) cout << bfs(i) << endl;
		else cout << res << endl;
	}

	return 0;
}