| 比赛 |
寒假集训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;
}