比赛 寒假集训5 评测结果 AAAAAEEEEE
题目名称 白色相簿的季节 最终得分 50
用户昵称 张雨晴 运行时间 1.035 s
代码语言 C++ 内存使用 34.25 MiB
提交时间 2026-03-01 11:32:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int M=2005;
#define int long long
typedef pair<int,int> PII;
int n,q,k;
int a[M];
int h[M],nxt[M],to[M],val[M],cnt;
void add(int u,int v,int w){
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=h[u];
    h[u]=cnt;
}
int dis[M][M],b[M];
void dij(int st){
    memset(b,0,sizeof(b));
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0,st});
    dis[st][st]=0;
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(b[u]==1) continue;
        b[u]=1;
        for(int i=h[u];i;i=nxt[i]){
            int v=to[i];
            if(b[v]) continue;
            if(dis[st][u]+val[i]<dis[st][v]){
                dis[st][v]=dis[st][u]+val[i];
                q.push({dis[st][v],v});
            }
        }
    }
//    for(int i=1;i<=n;i++){
//        cout<<i<<" "<<dis[st][i]<<"\n";
//    }
}
signed main(){
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout);
    
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>q>>k;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=k;i++){
        cin>>a[i];
        dij(a[i]);
//        cout<<"\n";
    }
    while(q--){
        int s,t;
        cin>>s>>t;
        int ans=1e15;
        for(int i=1;i<=k;i++){
            ans=min(ans,dis[a[i]][s]+dis[a[i]][t]);
        }
        cout<<ans<<"\n";
    }
    return 0;
}