# Opening Portals

## 题目描述

Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience.
This country has $n$ cities connected by $m$ bidirectional roads of different lengths so that it is possible to get from any city to any other one. There are portals in $k$ of these cities. At the beginning of the game all portals are closed. When a player visits a portal city, the portal opens. Strange as it is, one can teleport from an open portal to an open one. The teleportation takes no time and that enables the player to travel quickly between rather remote regions of the country.
At the beginning of the game Pavel is in city number $1$. He wants to open all portals as quickly as possible. How much time will he need for that?

## 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h[100001], p[100001], d[100001], fa[100001], pre[100001];
bool in[100001];
struct edge { long long v, w, nxt; } e[200001];
struct line {
long long u, v, w;
bool operator < (const line &a) const {
return d[u] + w + d[v] < d[a.u] + a.w + d[a.v];
}
} l[200001];
void add_edge(long long u, long long v, long long w) {
e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void spfa() {
queue<long long> que;
while (!que.empty()) que.pop();
for (int i = 1; i <= n; ++i)
if (!d[i]) in[i] = true, que.push(i);
while (!que.empty()) {
int u = que.front(); in[u] = false, que.pop();
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w, pre[e[i].v] = pre[u];
if (!in[e[i].v]) in[e[i].v] = true, que.push(e[i].v);
}
}
}
long long get_fa(long long t) {
return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
long long u, v, w; cin >> u >> v >> w; add_edge(u, v, w);
}
memset(d, 0x1f, sizeof d), d[1] = 0, spfa(); cin >> k;
for (int i = 1; i <= k; ++i) {
cin >> p[i]; if (d[p[i]] < mi) mi = d[p[i]];
}
ans = mi, memset(d, 0x1f, sizeof d);
for (int i = 1; i <= n; ++i) fa[i] = i, pre[i] = i;
for (int i = 1; i <= k; ++i) d[p[i]] = 0; spfa();
for (int i = 1; i <= n; ++i)
for (int j = h[i]; j; j = e[j].nxt)
l[++tot].u = i, l[tot].v = e[j].v, l[tot].w = e[j].w;
sort(l + 1, l + tot + 1);
for (int i = 1; i <= tot; ++i) {
long long u = get_fa(pre[l[i].u]), v = get_fa(pre[l[i].v]);
if (u != v) fa[u] = v, ans += d[l[i].u] + l[i].w + d[l[i].v];
}
cout << ans << endl;
return 0;
}


418 I'm a teapot