略水的题

本题提及的所有最短路本人均用dijkstra，还不会的出门左转

思路

这道题和2026紫堡杯T3很像，都用的是同一个思路。

题目在输入的时候就用的是“如果$U_i==0$，则表示该传送器的一端连接城镇 $V_i$​，另一端尚未确定。"这是不是就提示我们建立一个临时的点$0$，把未知的边当作已知的边，每一次询问就是在$0$和$i$之间建立一个边权$0$的边。

但是这样子每一次询问都暴力会TLE，我们还得优化。仔细思考一下，从$1$点到$n$点会分两种情况，经过$0$点和不经过$0$点。对于第一种情况，在询问前预处理最短路即可。对于第二种情况，可以先从$1$号点到$0$号点，再从$i$号点到$n$号点，或者是从$1$号点到$i$号点，再从$0$号点到$n$号点（边都是双向的），最后给三种情况选min即可。

AC代码

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=3e5+10;
vector<int>G[N];
int d1[N],d2[N];
int n,m;
void dij(int d[],int st)
{
	priority_queue<PII,vector<PII>,greater<PII> >Q;
	Q.push({0,st});d[st]=0;
	while(!Q.empty())
	{
		int x=Q.top().second;Q.pop();
		for(int i:G[x])
		{
			_sleep(1);
			if(d[i]>d[x]+1)
			{
				d[i]=d[x]+1;
				Q.push({d[i],i});
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	memset(d1,0x3f,sizeof(d1));memset(d2,0x3f,sizeof(d2));
	dij(d1,1);dij(d2,n);
	for(int i=1;i<=n;i++)
	{
		int ans=min({d1[n],d1[0]+d2[i],d1[i]+d2[0]});
		if(ans==1061109567)printf("-1 ");
		else printf("%d ",ans);
	}
	return 0;
}