题解：P5845 [IOI2011] crocodile

xiao7_Mr_10_ · 2024-09-05 10:42:39 · 题解

题意不过多赘述。

你注意到正向考虑很难，不如倒着考虑从 k 个中电走向起点的最优解。

因为这个鳄鱼它每轮能够堵边，而且它够聪明。所以它每次一定是堵在某个最短路上的边。所以我们就不能走最短路，而是次短路。

所以我们就直接用次短路更新最短路就可以了。

时间复杂度 O((n+m) \log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Point{
    int v,val;
    bool operator <(const Point &y)const{
        return val>y.val;
    }
};
int n,m,u,v,dis1[N],k,x,w,dis2[N];
vector <Point> e[N];
priority_queue <Point> q;
bool vis[N];
void dij(){
    while(!q.empty()){
        Point head=q.top();
        q.pop();
        if(vis[head.v])continue;
        vis[head.v]=1;
        for(int i = 0;i < e[head.v].size();i++){
            int v=e[head.v][i].v;
            if(dis1[v]>dis2[head.v]+e[head.v][i].val){
                dis2[v]=dis1[v],dis1[v]=dis2[head.v]+e[head.v][i].val;
                q.push((Point){v,dis2[v]});
            }
            else if(dis2[v]>dis2[head.v]+e[head.v][i].val){
                dis2[v]=dis2[head.v]+e[head.v][i].val;
                q.push((Point){v,dis2[v]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    memset(dis1,0x3f,sizeof(dis1));
    memset(dis2,0x3f,sizeof(dis2));
    for(int i = 1;i <= m;i++){
        cin >> u >> v >> w;u++,v++;
        e[u].push_back((Point){v,w});
        e[v].push_back((Point){u,w});
    }
    for(int i = 1;i <= k;i++){
        cin >> u;u++;
        dis1[u]=dis2[u]=0ll;
        q.push((Point){u,0});
    }
    dij();
    cout << dis2[1];
    return 0;
}