P5845 [IOI 2011] crocodile 题解

Pop_Agoni · 2025-11-18 22:28:53 · 题解

P5845 [IOI 2011] crocodile

前言：

简单题，仔细思考一下就可以了。

正解：

发现对于每个点 i 来说，鳄鱼会挡住它走最短路的那条边。

而且是对于每个点都会挡住。

那么肯定是和次短路有关系的。

但是肯定是和正常的最短路更新不太一样。

考虑到永远都只能走次短路，那么我们肯定是用次短路来更新。

没了？没了。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,m,k;
int dis[N],dis2[N];
bool vis[N];
vector<pair<int,int> > d[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        d[u].pb({v,w}),d[v].pb({u,w});
    }
    for(int i=0;i<=n;i++) dis[i]=1e9,dis2[i]=1e9,vis[i]=0;
    for(int i=1,x;i<=k;i++) scanf("%d",&x),dis[x]=dis2[x]=0,q.push({0,x});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0,v,w;i<d[u].size();i++){
            v=d[u][i].first,w=d[u][i].second;
            if(dis[v]>dis2[u]+w){
                dis2[v]=dis[v],dis[v]=dis2[u]+w;
                q.push({dis2[v],v});
            }
            else dis2[v]=min(dis2[v],dis2[u]+w),q.push({dis2[v],v});
        }
    }
    printf("%d\n",dis2[0]);
    return 0;
}