## Editorial for Bedao Grand Contest 05 - GFPROB

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#### Code mẫu

#include <bits/stdc++.h>

using namespace std;
const string filename = "GFPROB";

#define int long long

typedef pair<int,int> ii;
typedef pair<int,ii> iii;

int n,m,k,s;
int par[100001];
int a[100001], d[100001], p[100001];

int anc(int x)
{
if (par[x] == x) return x;
return par[x] = anc(par[x]);
}

void join(int x,int y)
{
par[anc(x)] = anc(y);
}

int res = 0;

void cal_d()
{
priority_queue<ii, vector<ii>, greater<ii>> pq;
for (int i=1;i<=n;i++)
{
par[i] = i;
d[i] = 1e18;
}
for (int i=1;i<=k;i++)
{
int x = a[i];
d[x] = 0; p[x] = x;
pq.push(ii(0,x));
}
while(!pq.empty())
{
int du = pq.top().first;
int u = pq.top().second;
pq.pop();
if (du != d[u])
continue;
{
int v = AdjList[u][i].first;
int w = AdjList[u][i].second;
if (d[v] > du + w)
{
p[v] = p[u];
d[v] = du + w;
pq.push(ii(d[v],v));
}
}
}
}

int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

freopen( (filename + ".inp").c_str(), "r", stdin);
freopen( (filename + ".out").c_str(), "w", stdout);

cin >> n >> m >> s >> k;
for (int i=1;i<=k;i++)
cin >> a[i];
while(m--)
{
int u,v,w;
cin >> u >> v >> w;
}
cal_d();
vector<iii> c;
for (int u=1;u<=n;u++)
{
int v = AdjList[u][i].first;
int w = AdjList[u][i].second;
c.push_back(iii(d[u] + d[v] + w,ii(p[u],p[v])));
}
sort(c.begin(),c.end());
int cnt = 0;
for (int i=0;i<c.size();i++)
{
int w = c[i].first;
int u = c[i].second.first;
int v = c[i].second.second;
if (anc(u) != anc(v))
{
res += w;
join(u,v);
}
if (cnt == k-1)
break;
}
cout << res + d[s];
}