牛客網 - 旅行商問題(路徑問題)

題目連結: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

輸出

解題思路

可以看到題目并不難，首先儲存所有路徑長度的和ans，找到一條1到所有點的最短路徑長度最大的，最後的答案就是ans的二倍再減去這條最大的路徑長度。

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

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