原题链接

第一份代码

#include<bits/stdc++.h>
#define ll long long
const ll maxs=2e18;
using namespace std;

ll e[1000005];
ll d[1000005];

struct node
{
    ll to,len;
    bool operator <(const node &b)const
    {
        return b.len>len;
    }
};

vector<node> G[1000006];

ll dis[1000006]={0};

struct fresh
{
    int pos,val,fa;
    bool operator<(const fresh &b) const
    {
        return val>b.val;
    }
};
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=1;i<=k;i++) cin>>e[i];

        for(int i=1;i<=n;i++) cin>>d[i];

        for(int i=1;i<=m;i++)
        {
            int x,y,w;
            cin>>x>>y>>w;
            G[x].push_back({y,w});
            G[y].push_back({x,w});
        }

        for(int i=1;i<=n;i++)
        {
            sort(G[i].begin(),G[i].end());
            dis[i]=maxs;
        }
        priority_queue<fresh> q;
        q.push({1,0,0});

        while(q.size())
        {
            int now=q.top().pos,val=q.top().val,fa=q.top().fa;
            q.pop();
            if(dis[now]<=val) continue;
            dis[now]=val;

            int cnt=d[now];
            //printf("d:%d\n",cnt);
            for(int i=0;i<G[now].size();i++)
            {
                int next=G[now][i].to,len=G[now][i].len;
                //printf("now:%d  next:%d  len:%d\n",now,next,len);

                if(next==fa) continue;
                if(cnt)
                {
                    cnt--;
                    continue;
                }

                //printf("now:%d next:%d len:%d\n",now,next,len);
                if(dis[now]+len<dis[next])q.push({next,dis[now]+len,now});
            }
        }

        ll ans=maxs;
        for(int i=1;i<=k;i++) ans=min(ans,dis[e[i]]);
        if(ans!=maxs) cout<<ans<<"\n";
        else cout<<"-1\n";
        for(int i=1;i<=n;i++)
        {
            G[i].clear();
        }
    }
    return 0;
}

错因分析

怎么保证封堵的路一定是到出口最短的？而不只是前往下一个节点最短的？

正解

当前集合到另外一个集合的最短路封住

code