Sunday, March 25, 2012

[code] TIOJ - 1212 最遠距點對

http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1213

先隨便戳一個點(第一個)

找出離他最遠的點

再從那個點再做一次DFS

P.S. 這題是多測資...害我WA了好幾次= =



#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct {
    int to, cost;
} edge;
vector<edge> G[100001];
int max_v, max_d;
bool used[100001] = {false};
void dfs(int v, int d)
{
    used[v] = true;
    if (d > max_d) {
        max_v = v;
        max_d = d;
    }
    for (int i = 0; i < G[v].size(); i++) {
        edge e = G[v][i];
        if (!used[e.to]) {
            dfs(e.to, d + e.cost);
        }
    }
    return ;
}
int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n) {
        for (int i = 0; i <= n; i++) {
            G[i].clear();
        }
        for (int i = 0; i < n - 1; i++) {
            int s, t;
            edge e;
            scanf("%d%d%d", &s, &t, &(e.cost));
            e.to = t;
            G[s].push_back(e);
            e.to = s;
            G[t].push_back(e);
        }
        memset(used, false, sizeof(used));
        max_d = 0;
        max_v = 1;
        dfs(1, 0);
        memset(used, false, sizeof(used));
        max_d = 0;
        dfs(max_v, 0);
        printf("%d\n", max_d);
    }
    return 0;
}
 

No comments:

Post a Comment