自动搬运

查看原文

来自洛谷，原作者为

	liaoxingrui 壶关

搬运于2025-08-24 22:50:26，当前版本为作者最后更新于2024-06-12 17:01:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Content

给你一个 $n$ 点与 $m$ 条边组成的有权无向图，起点为 $1$ 号点，终点有 $k$ 个，第 $i$ 个出口在 $e_i$，每经过一个点 $i$ 都会随机封锁至多 $d_i$ 条与之相邻的道路，使得你到出口距离最大，但离开后就会解封。

现在问到达任意出口的距离最短是多少，若不能到达，则输出 -1。

Solution

因为它有 $k$ 个出口，并不知道到哪个出口更优，所以我们可以把 $k$ 个出口当作起点，把 $1$ 号店当作出口，这样 $dis_1$ 就是答案了。

接下来我们考虑 $d_i$，由于道路可能被封锁，所以我们要判断这个点是否还会封锁，如果会，那么就将这条路封锁了（因为这个权值是现在最优的），否则就将这个点赋值。

Code

#include<bits/stdc++.h>
#define p pair<int,int>
#define m(x,y) make_pair(x,y)
#define now next[i].x
#define vall next[i].val
using namespace std;
const int N=1e5+5;
const int M=3e6+5;
int t,n,m,k,x,y,z,tot;
int d[N],out[N],dis[N],head[N];
bool flag[N];
priority_queue<p,vector<p>,greater<p> > a;
struct node{
	int x,y,val;
}next[M];
inline void add(int x,int y,int z){
	tot++;
	next[tot].x=y;
	next[tot].y=head[x];
	next[tot].val=z;
	head[x]=tot;
}
inline void dijkstra(){
	while(!a.empty()){
		int x=a.top().second,val=a.top().first;
		a.pop();
		if(d[x]){
			d[x]--;
			continue;
		}
		if(flag[x])
			continue;
		flag[x]=true;
		dis[x]=val;
		for(int i=head[x];i;i=next[i].y)
			if(!flag[now])
				a.push(m(val+vall,now));
	}
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++){
		    dis[i]=-1;
		    head[i]=flag[i]=0;
		}
		for(int i=1;i<=k;i++){
			cin>>out[i];
			dis[out[i]]=0;
			a.push(m(0,out[i]));
		}
		for(int i=1;i<=n;i++)
			cin>>d[i];
		for(int i=1;i<=k;i++)
		    d[out[i]]=0;
		while(m--){
			cin>>x>>y>>z;
			add(x,y,z);
			add(y,x,z);
		}
		dijkstra();
		cout<<dis[1]<<endl;
	}
	return 0;
}