ZOJ4136 Escape Plan（最短路）

这个题有一个限制条件，就是每个位置会有d个怪物，题目告诉我们他会挡住d条路，并且要我们计算在最坏情况下的最短路。

最坏情况，就是阻挡我到达这个点之后，往外的前d小的路。因此这是一个多元变种迪杰斯特拉，在普通的多元迪杰斯特拉的情况

我们注意每个点的d状态，忽视前d个到达这个点的答案，这样跑出来的就是最后的答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pll;
const int N=2e6+10;
const int inf=0x3f3f3f3f;
int h[N],ne[N],e[N],idx;
int n,m,k;
int pos[N];
ll dis[N],st[N];
int d[N],w[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dij(){
    int i;
    for(i=1;i<=n;i++){
        dis[i]=1e18;
        st[i]=0;
    }
    priority_queue<pll,vector<pll>,greater<pll> > q;
    for(i=1;i<=k;i++){
        q.push({0,pos[i]});
        dis[pos[i]]=0;
        d[pos[i]]=0;
    }
    while(q.size()){
        auto t=q.top();
        q.pop();
        if(d[t.second]){
            d[t.second]=max(d[t.second]-1,0);
            continue;
        }
        if(st[t.second]){
            continue;
        }
        st[t.second]=1;
        dis[t.second]=t.first;
        for(i=h[t.second];i!=-1;i=ne[i]){
            int j=e[i];
            if(st[j])
                continue;
            q.push({t.first+w[i],j});
        }
    }
    if(dis[1]==1e18)
        cout<<-1<<endl;
    else
    cout<<dis[1]<<endl;
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int i;
        idx=0;
        cin>>n>>m>>k;
        for(i=1;i<=n;i++)
            h[i]=-1;
        for(i=1;i<=k;i++){
            cin>>pos[i];
        }
        for(i=1;i<=n;i++){
            cin>>d[i];
        }
        for(i=1;i<=m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
        }
        dij();
    }
    return 0;
}