比赛 寒假集训5 评测结果 AAAWWWWWWT
题目名称 白色相簿的季节 最终得分 30
用户昵称 梦那边的美好ME 运行时间 1.480 s
代码语言 C++ 内存使用 6.53 MiB
提交时间 2026-03-01 10:43:59
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,q,k,kk;
ll head[110000],nxt[210000],to[210000],val[210000],cnt;
ll dis[110000];
bool vis[110000];

void add(ll u,ll v,ll w){
	to[++cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

int dijkstra(ll s){
	for (int i=1;i<=n;i++){
		dis[i]=2e9;
		vis[i]=0;
	}
	dis[s]=0;
	priority_queue <pair<ll,ll> > qq;
	qq.push(make_pair(0,s));
	while (!qq.empty()){
		ll u=qq.top().second;qq.pop();
		if (vis[u]) continue;
		vis[u]=1;
		for (int i=head[u];i;i=nxt[i]){
			ll v=to[i],w=val[i];
			if (dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				qq.push(make_pair(-dis[v],v));
			}
		}
	}
	return 0;
}

int main(){
	freopen("wa.in","r",stdin);
	freopen("wa.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q>>k;
	for (int i=1;i<n;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	for (int i=1;i<=k;i++){
		cin>>kk;
	}
	while (q--){
		ll s,t;
		cin>>s>>t;
		if (k==n){
			dijkstra(s);
			cout<<dis[t]<<'\n';
		}else if (k==1){
			dijkstra(kk);
			cout<<dis[s]+dis[t]<<'\n';
		}
	}
	return 0;
}