我们先考虑如果所有点都是特殊点， 那么就是对整个图求个MST。 想在如果不是所有点是特殊点的话， 我们能不能也
转换成求MST的问题呢？ 相当于我们把特殊点扣出来， 然后求出两两之间的最短路， 然后求MST， 但直接这样暴力做
肯定不行。 我们先跑个多元最短路， 找到离 i 最近的特殊点 p[ i ]， 并且距离为d[ i ]。 对于每两个特殊点a, b之间的最短路
我们都能找到一条边(u, v, w)对应它， 并且p[ u ] = a, p[ v ] = b， 且在所有的p[ u ] = a, p[ v ] = b的边中 d[ u ] + d[ v ] + w
是最小的那个， 这就是a, b之间的最短路。 我们将边排序之后， 跑克鲁斯卡尔就好啦。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = ;
const double eps = 1e-;
const double PI = acos(-); int n, m, a[N], k;
vector<PLI> G[N]; LL d[N];
int p[N]; int fa[N];
int getRoot(int x) {
return x == fa[x] ? x : fa[x] = getRoot(fa[x]);
} pair<PII, int> e[N];
int id[N]; bool cmp(const int& a, const int& b) {
return d[e[a].fi.fi] + d[e[a].fi.se] + e[a].se < d[e[b].fi.fi] + d[e[b].fi.se] + e[b].se;
} int main() {
memset(d, INF, sizeof(d));
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i <= m; i++) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
e[i].fi.fi = x, e[i].fi.se = y, e[i].se = w;
G[x].push_back(mk(w, y));
G[y].push_back(mk(w, x));
id[i] = i;
}
scanf("%d", &k);
priority_queue<PLI, vector<PLI>, greater<PLI> > que;
for(int i = ; i <= k; i++) {
scanf("%d", &a[i]);
p[a[i]] = a[i];
d[a[i]] = ;
que.push(mk(, a[i]));
}
while(!que.empty()) {
int u = que.top().se;
LL dis = que.top().fi;
que.pop();
if(dis > d[u]) continue;
for(auto& e : G[u]) {
if(dis + e.fi < d[e.se]) {
d[e.se] = dis + e.fi;
p[e.se] = p[u];
que.push(mk(d[e.se], e.se));
}
}
}
LL ans = ;
sort(id + , id + + m, cmp);
for(int i = ; i <= m; i++) {
int u = p[e[id[i]].fi.fi];
int v = p[e[id[i]].fi.se];
LL w = e[id[i]].se + d[e[id[i]].fi.fi] + d[e[id[i]].fi.se];
int x = getRoot(u);
int y = getRoot(v);
if(x != y) {
fa[y] = x;
ans += w;
}
}
ans += d[];
printf("%lld\n", ans);
return ;
} /*
*/