题解：P11966 [GESP202503 八级] 上学

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,b[200001],d[200001],qd;
vector<pair<long long,long long>>a[200001];
set<pair<long long,long long>>c;
void dijkstra(){
	for(long long i=1;i<=n;i++){
		b[i]=1e18;
		c.insert({b[i],i});
	}
	c.erase({b[qd],qd});
	c.insert({0,qd});
	b[qd]=0;
	for(;!c.empty();){
		long long x=(*c.begin()).second;
		c.erase(c.begin());
		for(auto j:a[x]){
			if(b[x]+j.second<b[j.first]){
				c.erase({b[j.first],j.first});
				b[j.first]=b[x]+j.second,d[j.first]=x;
				c.insert({b[j.first],j.first});
			}
		}
	}
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&qd,&t);
	for(long long i=1;i<=m;i++){
		long long x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		a[x].push_back({y,z});
		a[y].push_back({x,z});
	}
	dijkstra();
	for(long long i=1;i<=t;i++){
		long long x;
		scanf("%lld",&x);
		printf("%lld\n",b[x]);
	}
}