路线规划

题目链接：nowcoder 217603

到主站看：https://blog.csdn.net/weixin_43346722/article/details/113065389

题目大意

有一个图，要从一号节点出发经过所有点回到一号节点。
要你在走过的路最少的前提下，让总距离最短。

思路

首先，它要求路过所有的点，然后要走过的路最小。
因为道路双向，那我们可以原路返回（先不考虑距离的问题）。那我们可以想到至少要 个点，才可以把 个点遍历一遍，那其实就是一棵树。

现在我们已经知道了边的数量，我们就是要看距离了。
那我们考虑已经知道了树，看距离怎么求。那其实就是一个欧拉序，想跑 dfs 一个图一样，每条边分别过去和回来。就是每条边都经过两次，那距离就是树上每条边的长度的和的两倍。

那你怎么让树上每条边的距离的和最小呢？
没错，最小生成树。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

struct node {
    int x, y;
    long long z;
}a[2000001];
int n, m, fa[200001], num, X, Y;
long long ans;

bool cmp(node x, node y) {
    return x.z < y.z;
}

int find(int now) {
    if (fa[now] == now) return now;
    return fa[now] = find(fa[now]);
}

void connect(int x, int y) {
    X = find(x);
    Y = find(y);
    fa[X] = Y;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %lld", &a[i].x, &a[i].y, &a[i].z);
    }

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    sort(a + 1, a + m + 1, cmp);

    for (int i = 1; i <= m; i++) {//最小生成树
        X = find(a[i].x);
        Y = find(a[i].y);

        if (X != Y) {
            num++;
            ans += a[i].z;
            fa[X] = Y;
            if (num == n - 1) break;
        }
    }

    printf("%lld", ans * 2ll);//欧拉序，就是每个边走两遍

    return 0;
}