F - Teleporter Setting（建立虚点）

F - Teleporter Setting

题意：
给出n个顶点和一些边，其中一些边两个端点确定，另一些边只有一个端点确定，对于每个i，令其为所有这些不确定的边的另一个端点，问1到n的最短距离是多少。

建立一个虚点，然后f,g分别表示1，n到x的最短距离，
分别计算两种经过i的情况，以及可能不经过i的情况即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=3e5+10;
//const int S=1e5+5;
//const int inf=1ll<<60;
const int inf=1<<29;
const ll mo=1e9+7;
vector<int> e[N];
int n,m,f[N],g[N],x,y;
queue<int> q;
bool vis[N];
void bfs(int s,int *d){
	fo(i,1,n+1)	d[i]=inf;
	memset(vis,0,sizeof(vis));
	
	vis[s]=1;
	d[s]=0;
	q.push(s);
	while (!q.empty()) {
		x=q.front(); q.pop();
		for (int v:e[x]) {
			d[v]=min(d[v], d[x]+1);
			if (!vis[v]) {
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
int main()
{
//	freopen("data.in","r",stdin);
	
	scanf("%d %d",&n,&m);
	fo(i,1,m) {
		scanf("%d %d",&x,&y);
		if (!x) x=n+1;
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}
	
	bfs(1, f);
	bfs(n, g);
	
	fo(i,1,n) {
		int ans=min(f[i]+g[n+1], f[n+1]+g[i]);
		ans=min(ans, f[n]);
		printf("%d ",ans<n ? ans:-1);
	}
	
	return 0;
}