比赛 寒假集训5 评测结果 WAAAAWEEWE
题目名称 白色相簿的季节 最终得分 40
用户昵称 ychyyx 运行时间 1.072 s
代码语言 C++ 内存使用 8.67 MiB
提交时间 2026-03-01 09:34:35
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
int n,k;
int u,v,w;
int a[100005];
bool bj[5005];
int m;
int s,t;
ll dis[5005][5005];
struct node{
    int to,val;
};
struct Node{
    int u;
    long long val;
    bool operator<(const Node &b) const{
        return val<b.val||val==b.val&&u<b.u;
    }
};
priority_queue<Node> q;
vector<node> g[100005];
int f[5005],dep[5005];
void dfs(int u,int fa){
    f[u]=fa;
    dep[u]=dep[fa]+1;
    for(auto it:g[u]){
        int v=it.to;
        if(v==fa)   continue;
        dfs(v,u);
    }
}
int main(){
    freopen("wa.in","r",stdin);
    freopen("wa.out","w",stdout); 
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int i=1;i<=k;i++)    scanf("%d",&a[i]);
    if(n!=k)
        for(int i=1;i<=k;i++){
            for(int j=1;j<=n;j++)   dis[a[i]][j]=1e18,bj[j]=0;
            dis[a[i]][a[i]]=0;
            q.push({a[i],0});
            while(!q.empty()){
                u=q.top().u;
                q.pop();
                if(bj[u])   continue;
                bj[u]=1; 
                for(auto it:g[u]){
                    v=it.to,w=it.val;
                    if(dis[a[i]][v]>dis[a[i]][u]+w){
                        dis[a[i]][v]=dis[a[i]][u]+w;
                        q.push({v,dis[a[i]][v]});
                    }
                }
            }
        }
    for(;m--;){
        scanf("%d%d",&s,&t);
        if(n==k){
            printf("0\n");
        }else{
            ll ans=1e18;
            for(int i=1;i<=k;i++)
                ans=min(ans,dis[a[i]][s]+dis[a[i]][t]);
            printf("%lld\n",ans);       
        }
    }
    return 0;
}