题目链接:https://ac.nowcoder.com/acm/contest/547/E
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述 

旅行商来到了一个新的国家，这个国家有N个城市，他们直接由N-1条道路相连接，每条道路的长度不尽相同
旅行商现在在1号城市，若他要每一个城市都游览一遍，他需要行走的最短路程是多少？

输入描述:

第一行一个数N （50000>N>1）
代表城市个数
之后N-1行
每行三个数x y z
代表从x到y的距离为z

输出描述:

输出最小距离

输入

3
1 2 1
1 3 1

输出

3

解题思路

可以看到题目并不难，首先保存所有路径长度的和ans，找到一条1到所有点的最短路径长度最大的，最后的答案就是ans的二倍再减去这条最大的路径长度。

深搜+vector:

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int v;
    long long w;
};
int vis[50005];
long long ans, max_;
vector <edge> a[50005];
void DFS(int s, long long dis) {
    vis[s] = 1;
    int len = a[s].size();
    if (len == 1 && vis[a[s][0].v]) {
        max_ = max(max_, dis);
        return ;
    }
    for (int i = 0; i < len; i++) {
        if (!vis[a[s][i].v]) {
            DFS(a[s][i].v, dis + a[s][i].w);
        }
    }
}
int main() {
    int n, u, v, w;
    scanf("%d", &n);
    ans = max_ = 0;
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        a[u].push_back((edge){v, w});
        a[v].push_back((edge){u, w});
        ans += w;
    }
    DFS(1, 0);
    printf("%lld\n", (ans << 1) - max_);
}

深搜+邻接表:

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int u, v;
    long long w;
}e[100005];
int cnt = 0, f[50005];
long long ans, max_;
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void DFS(int s, int t, long long dis) {
    for (int i = f[s]; i; i = e[i].u) {
        int v = e[i].v;
        if (v != t)
            DFS(v, s, dis + e[i].w);
        max_ = max(max_, dis);
    }
}
int main() {
    int n, u, v, w;
    scanf("%d", &n);
    ans = max_ = 0;
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        Add(u, v, w);
        Add(v, u, w);
        ans += w;
    }
    DFS(1, 0, 0);
    printf("%lld\n", (ans << 1) - max_);
    return 0;
}

Spfa:

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int u, v;
    long long w;
}e[100005];
long long ans, max_, dis[50005];
int cnt = 0, f[50005], vis[50005];
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s) {
    queue <int> Q;
    Q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
        int t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int i = f[t]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] > dis[t] + e[i].w) {
                dis[v] = dis[t] + e[i].w;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    int n, u, v;
    long long w;
    scanf("%d", &n);
    ans = max_ = 0;
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i < n; i++) {
        scanf("%d%d%lld", &u, &v, &w);
        Add(u, v, w);
        Add(v, u, w);
        ans += w;
    }
    Spfa(1);
    for (int i = 2; i <= n; i++)
        max_ = max(max_, dis[i]);
    printf("%lld\n", (ans << 1) - max_);
    return 0;
}