比赛 寒假集训5 评测结果 AAATTTTTTT
题目名称 白色相簿的季节 最终得分 30
用户昵称 杨蕙宇 运行时间 7.904 s
代码语言 C++ 内存使用 8.42 MiB
提交时间 2026-03-01 10:25:16
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int n,Q,k,key[N],dis[N],mk[N];
struct edge{
    int v,w;
};
struct node{
    int dis,u;
    bool operator>(const node& a)const{
        return dis>a.dis;
    }
};
vector<edge>e[N];
vector<int>ky;

void dijkstra(int s,int t){
    for(int i=0;i<=n;i++)dis[i]=INF;
    memset(mk,0,sizeof(mk));
    priority_queue<node, vector<node>, greater<node>> q;
    dis[s]=0;
    q.push({0,s});
    dis[s]=0;
    while(q.size()){
        if(mk[t])return;
        int u=q.top().u;
        q.pop();
        if(mk[u])continue;
        mk[u]=1;
        for(auto ed:e[u]){
            int v=ed.v;
            int w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
    
}
int main(){
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    cin>>n>>Q>>k;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        key[x]=1;
        ky.push_back(x);
    }
    while(Q--){
        int s,t;
        cin>>s>>t;
        int ans=INF,a,b;
        if(key[s]||key[t]){
            dijkstra(s,t);
            ans=dis[t];
        }
        else if(!key[s]&&!key[t]){
           for(int i=0;i<ky.size();i++){
               dijkstra(ky[i],s);
               a=dis[s];
               dijkstra(ky[i],t);
               b=dis[t];
               ans=min(ans,a+b);
           } 
        }
        cout<<ans<<endl;
    }
    return 0;
}