自动搬运

查看原文

来自洛谷，原作者为

	zhouhuanyi 在量子世界中，所有的未来都同样真实。

搬运于2025-08-24 22:14:55，当前版本为作者最后更新于2020-01-21 14:55:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$[IOI2011]crocodile$

这题没有题解，我就来发一篇。

链接：https://www.luogu.com.cn/problem/P5845

题目描述:给定出发点$s$与$k$个终点，有一个鳄鱼门卫可以在每一轮堵住一条边，求最坏情况下走到终点要多长时间。

题解:从出发点像终点考虑十分复杂，不妨从终点向出发点考虑，由于鳄鱼门卫会挡住一条边，所以从一个与终点相邻的点到终点的最短路径一定会被挡住，只能走次短路。由于到该点的路是次短路，所以我们只能用次短路更新。以此类推，每个点每一次用到自己的次短路去扩展即可。

#include<iostream>
#include<queue>
using namespace std;
struct node
{
	int v,data,nxt;
};
node edge[10000001];
struct reads
{
	int num,data;
	bool operator < (const reads &a)const
	{
		return data>a.data;
	}
};
reads tmp;
int head[10000001],len;
int n,m,dis[10000001],dis2[10000001];
bool used[10000001];
priority_queue<reads>q;
void add(int x,int y,int z)
{
	edge[++len].v=y;
	edge[len].data=z;
	edge[len].nxt=head[x];
	head[x]=len;
	return;
}
reads make_reads(int x,int y)
{
	tmp.num=x;
	tmp.data=y;
	return tmp;
}
void dijkstra()
{
	int top;
	while (!q.empty())
	{
		top=q.top().num;
		q.pop();
		if (used[top])
			continue;
		used[top]=1;
		for (int i=head[top];i>0;i=edge[i].nxt)
		{
			if (dis[edge[i].v]>dis2[top]+edge[i].data)
			{
				dis2[edge[i].v]=dis[edge[i].v];
				dis[edge[i].v]=dis2[top]+edge[i].data;
				q.push(make_reads(edge[i].v,dis2[edge[i].v]));
			}
			else if (dis2[edge[i].v]>dis2[top]+edge[i].data)
			{
				dis2[edge[i].v]=dis2[top]+edge[i].data;
				q.push(make_reads(edge[i].v,dis2[edge[i].v]));
			}
		}
	}
	cout<<dis2[0]<<endl;
	return;
}
int main()
{
	int k,x,y,z;
	cin>>n>>m>>k;
	for (int i=0;i<=n-1;++i)
		dis[i]=dis2[i]=1e9;
	for (int i=1;i<=m;++i)
	{
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	for (int i=1;i<=k;++i)
	{
		cin>>x;
		dis[x]=dis2[x]=0;
		q.push(make_reads(x,0));
	}
	dijkstra();
	return 0;
}