[UVa] 10308 Roads in the North.cpp

#include <cstdio>
#include <vector>
using namespace std;
struct point_type{
    int nxt;
    int len;
};
vector<point_type> toPoint[10005];
int ans;
int DFS(int point, int prev_point) // DFS回傳該點能走的最深路徑的距離
{
    int route_max = 0;
    for (auto &p : toPoint[point]) {
        if (p.nxt == prev_point) continue;

        int route = DFS(p.nxt, point) + p.len;

        if (route + route_max > ans) // 現在走的路徑+已經儲存的最大路徑如果大於ans就更新ans
            ans = route + route_max;

        if (route > route_max)
            route_max = route;
    }
    return route_max;
}
void input(char line[])
{
    int p1, p2, L;
    sscanf(line, "%d%d%d", &p1, &p2, &L);
    toPoint[p1].push_back({p2,L});
    toPoint[p2].push_back({p1,L});
}
int main()
{
    freopen("input.txt","rt",stdin);
    char line[100];
    while (gets(line)) {
        if (line[0] == '\0') {
            puts("0");
            continue;
        }
        for (auto &v : toPoint) v.clear();
        input(line);

        while (gets(line)) {
            if (line[0] == '\0') break;
            input(line);
        }

        ans = 0;
        DFS(1,-1);
        printf("%d\n", ans);
    }
    return 0;
}