POJ 2631 DFS+带权无向图最长路径

http://poj.org/problem?id=2631

2333水题，

有一个小技巧是说随便找一个点作为起点，

找到这个点的最远点，

以这个最远点为起点，

再次找到的最远点就是这个图的最远点

证明可以用三角形定理

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

#define maxn 10005

using namespace std;

struct donser

{

    int tow;

    int dis;

};

vector<donser> vec[maxn];

int maxdistances=,distances=,maxtown=;

bool used[maxn];

void maxway(int x)

{

    int way=vec[x].size(),i=;

    struct donser a;

    //cout<<"?x:"<<x<<" vec[x].size():"<<way<<endl;

    while(i<way)

    {

        a=vec[x].at(i);

        i++;

        if(used[a.tow]) continue;

        distances+=a.dis;

        //cout<<"+a.dis:"<<a.dis<<endl;

        used[a.tow]=;

        maxway(a.tow);

        if(distances>=maxdistances)

        {

            maxdistances=distances;

            maxtown=a.tow;

        }

        used[a.tow]=;

        //cout<<"-a.dis:"<<a.dis<<endl;

        distances-=a.dis;

    }

    return;

}

int main()

{

    int a,b,dist;

    struct donser num;

    //freopen("in.txt","r",stdin);

    while(~scanf("%d%d%d",&a,&b,&dist))

    {

        num.tow=b;

        num.dis=dist;

        vec[a].push_back(num);

        num.tow=a;

        vec[b].push_back(num);

    }

    used[]=;

    maxway();

    distances=;

    //cout<<"!maxtown"<<maxtown<<"!maxdistances"<<maxdistances<<endl;

    memset(used,,sizeof(used));

    maxway(maxtown);

    //cout<<"!maxtown"<<maxtown<<"!maxdistances"<<maxdistances<<endl;

    cout<<maxdistances<<endl;

    return ;

}