P9650 [SNCPC2019] Escape Plan

liaoxingrui · 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;
}