堆优化DIJ

#include<iostream>
#include<queue>
#include<vector>
#define int long long
using namespace std;

struct node{
int u,dis;
bool operator>(const node o) const{
return dis > o.dis;
}
};
struct edge{
int to,val;
};
int n,m,s,q;
vector<int> d,h;
vector<vector<edge>> mp;
priority_queue<node,vector<node>,greater<node> pq;
void in(){
cin >> n >> m >> s >> q;
d.resize(n + 5,1e18),mp.resize(n + 5);
while(m--){
int u,v,w;
cin >> u >> v >> w;
mp[u].push_back({v,w}),mp[v].push_back({u,w});
}
while(q--){
int x;
cin >> x;
h.push_back(x);
}
}
void solve(){
pq.push({s,0});
d[s] = 0;
while(!pq.empty()){
int r = pq.top().u,dist = pq.top().dis;
pq.pop();
if(dist > d[r]) continue;
d[r] = dist;
for(auto next : mp[r]){
if(dist + next.val < d[next.to]){
d[next.to] = dist + next.val;
pq.push({next.to,d[next.to]});
}
}
}
for(auto i : h){
cout << d[h] << endl;
}
}
signed main(){
in();
solve();

return 0;

}