题解：P11966 [GESP202503 八级] 上学

laiyouming · 2025-03-31 10:14:41 · 题解

思路

我们发现图是双向的。x 到 y 的距离等于 y 到 x 的距离。所以我们可以从学校进行一遍最短路。来统计答案。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,b[200001],d[200001],qd;
vector<pair<long long,long long>>a[200001];
set<pair<long long,long long>>c;
void dijkstra(){
    for(long long i=1;i<=n;i++){
        b[i]=1e18;
        c.insert({b[i],i});
    }
    c.erase({b[qd],qd});
    c.insert({0,qd});
    b[qd]=0;
    for(;!c.empty();){
        long long x=(*c.begin()).second;
        c.erase(c.begin());
        for(auto j:a[x]){
            if(b[x]+j.second<b[j.first]){
                c.erase({b[j.first],j.first});
                b[j.first]=b[x]+j.second,d[j.first]=x;
                c.insert({b[j.first],j.first});
            }
        }
    }
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&qd,&t);
    for(long long i=1;i<=m;i++){
        long long x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    dijkstra();
    for(long long i=1;i<=t;i++){
        long long x;
        scanf("%lld",&x);
        printf("%lld\n",b[x]);
    }
}