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?

题意概述

给定一张$n$个点$m$条边的无向图，其中$k$个点上有传送器，每条边都有一个权值。初始时所有传送器都处于关闭状态，你在$1$号点。你需要走到所有有传送器的点，将传送器打开。你可以从一个已经打开的传送器直接传送到另一个已经打开的传送器。求经过的所有边的权值和的最小值。

数据范围：$1 \le k \le n \le 10^5, \ 0 \le m \le 10^5$。

算法分析

我们假设所有的点都是传送器。根据最小生成树的性质，这时的最优解就是这张图的最小生成树。显然，如果我们把这张图抽象成只由$k$个有传送器的点构成的“传送图”，这时的最优解也就是“传送图”上的最小生成树。如何构造这张图呢？

计算出每个点到离它最近的传送器的位置$p_i$和距离$d_i$。对于一条权值为$w$的边$(u, v)$，我们将它想象一条权值为$(d_u+w+d_v)$的边$(p_u, p_v)$。这样，这张图上的所有边也就变成了连接$k$个传送器的边。这就可以用 Kruskal 求最小生成树来解决。这棵最小生成树的边权之和是固定的，因此当$1$号点没有传送器时，可以先走到离它最近的一个有传送器的点。

求$p_i$和$d_i$可以用多源 SPFA 来完成。

代码

#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;
}