思路
首先看到花最小代价使得所有点连通，果断转换成最小生成树问题。
接下来就要考虑怎么建图，首先陆地就正常连不用说，建机场和港口的代价貌似都是点权，考虑转成边权。因为一个点飞或者划船到另一个点要两重代价，所以若我们想让 \(u\) 和 \(v\) 建能飞过去的边，我们可以先从 \(u\) 建一条边权为 \(x[u]\) 的边到 \(t\)，再从 \(t\) 建一条边权为 \(x[v]\) 的边到 \(v\)。
我们按照上面的思路让每个点都和其余 \(n-1\) 个点这样建边就能得到一张完全图。这样建图虽然在意义上是没有问题的，但是再跑最小生成树时会强制性把所有无关的中转点也选进去，导致代价重复计算，而且是完全图，边数达到 \(O(n^2)\) 级别，光建图就 TLE 了。
我们可以这样去想：我们可以多建两个大点，表示一整片天空，和一整片海。每个点都要对着海和天空连一条边（听起来怎么有点浪漫），边权为自己建机场和港口的代价。这样我们就可以实现我们刚才想达到的所有目的了。
为什么呢？首先看第一个目的，为了解决点权转边权，我们也用了中转站解决，而且只要多建 \(2n\) 条边。那这样也有个问题，也不是非要走天和走海，万一走普通边最优呢。为了解决这个问题我们可以直接暴力跑 4 次最小生成树——
-
只开车
-
只飞天和开车
-
只航海和开车
-
又飞天又航海又开车
这样就完美解决了。至于最重要的一点，为什么只用所有点连到天空和海不影响图的结构？因为图的本质就是一堆点集和一堆描述联通关系的边。我们看第一版建边思路，点集只有 \(O(n)\)，但边数真的有必要这么多吗？
我们注意到每一个我们建的中转点连出去的点集都是一样的，因此有一个中转点就足够。而且对于每一个点，能达到的点和边权的状态都和有一个中转点的情况相同，所以没必要连成完全图，而是把属于这一类的所有边聚集到一个源点，将稠密图稀疏化，而且使得以前每个点能到达的点与边权的状态一样……
我们一般把这类 trick 叫做 建超级源点，聚集到的源点叫做 超级源点。当然这也只是超级源点的一种用法，之后更多好玩的用法大家可以多找点图论题找找，说不定那道题的题解也会是我写的。
实现
之后讲一下实现。也就是按上面的思路建 4 次边跑 4 次最短路，但有一些细节值得注意。
-
第 0 次跑最小生成树时，陆地上的边不一定能形成最小生成树，但是其他 3 次保证一定能形成最小生成树。
-
最多会有 \(3n\) 条边，数组要开够
-
做 4 次生成树要建 4 次边，而有些代码可以复用，可以使用一些模拟技巧缩短此题代码长度
代码
//
// main.cpp
// [ABC270F] Transportation
//
// Created by SkyWave Sun on 2023/11/30.
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <climits>
using namespace std;
typedef long long ll;
const int N = 2e5 + 1;
struct dsu {
vector<int> fa;
void resize(int sz) {
fa.resize(sz + 1);
iota(fa.begin(), fa.end(), 0);
}
dsu() {
}
dsu(int sz) {
resize(sz);
}
int findFa(int pos) {
return pos == fa[pos] ? pos : fa[pos] = findFa(fa[pos]);
}
void mergeFa(int u, int v) {
fa[findFa(u)] = findFa(v);
}
bool same(int u, int v) {
return findFa(u) == findFa(v);
}
};
struct Edge {
int u, v, w;
bool operator < (const Edge &e) const {
return w < e.w;
}
};
Edge e[N * 3];//注意数组大小
ll kruskal(int n, int m) {
sort(e + 1, e + m + 1);
dsu d(n);
ll ans = 0;
int cnt = 0;
for (int i = 1; i <= m; ++i) {
if (!d.same(e[i].u, e[i].v)) {
d.mergeFa(e[i].u, e[i].v);
ans += e[i].w;
++cnt;
}
if (cnt == n - 1) {
break;
}
}
return cnt == n - 1 ? ans : LONG_LONG_MAX;//不能形成最小生成树时返回无穷大不对最后答案产生影响
}
int x[N], y[N];
int u[N], v[N], w[N];
int main(int argc, const char * argv[]) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &y[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &u[i], &v[i], &w[i]);
}
ll ans = LONG_LONG_MAX;
for (int i = 0; i < 4; ++i) {//类似状压枚举复用建边代码
int source = n/*超级源点编号*/, rear = 0;
if (i & 1) {
++source;/*天上边超级源点为 n + 1*/
for (int j = 1; j <= n; ++j) {
e[++rear] = {source, j, x[j]};
}
}//在 i = 1、 3 的时候建天上边
if (i & 2) {
++source;/*海上边超级源点为 n + 2*/
for (int j = 1; j <= n; ++j) {
e[++rear] = {source, j, y[j]};
}
}//在 i = 2、3 的时候建海上边
for (int j = 1; j <= m; ++j) {
e[++rear] = {u[j], v[j], w[j]};
}//i = 0、1、2、3 都要建陆地边
ans = min(ans, kruskal(source, rear));
}
printf("%lld\n", ans);
return 0;
}