测试点信息

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200010, MAX_M = 400010;


long long n, m, s, q, head[MAX_N], vis[MAX_N]={0}, dis[MAX_N], cnt=0;

struct node{
	long long dis;
	int pos;
	bool operator < (const node& o) const{
		return o.dis < dis;
	}
};

struct edge{
	int to;
	long long dis;
	int next;
};


priority_queue<node> que;
edge e[MAX_M];


void add_edge(int u, int v, long long s){
	cnt++;
	e[cnt].to = v;
	e[cnt].dis = s;
	e[cnt].next = head[u];
	head[u] = cnt;
}


void dijiesitera(){
	while (!que.empty()){
		node tmp = que.top();
		int di = tmp.dis, pos = tmp.pos;
		que.pop();
		if (vis[pos]) continue;
		vis[pos] = 1;
		for (int i = head[pos];i;i = e[i].next){
			int vi = e[i].to, si = e[i].dis;
			if (dis[vi] > dis[pos] + si){
				dis[vi] = di +si;
				node pl = {dis[vi], vi};
				que.push(pl);
			}
		}
	}
}


int main(){
	cin>>n>>m>>s>>q;
	for (int i=1;i<=m;++i){
		int ui, vi, si;
		cin>>ui>>vi>>si;
		add_edge(ui, vi, si);
		add_edge(vi, ui, si);
	}
	for (int i=1;i<=n;++i) dis[i] = LLONG_MAX;
	dis[s] = 0;
	node n_f = {0, s};
	que.push(n_f);
	dijiesitera();
	for (int i=1;i<=q;++i){
		int qi;
		cin>>qi;
		cout<<dis[qi]<<endl;
	}
	return 0;
}