转载请注明出处：

思路：从任意一点a开始找到最长路径的终点为b， 在从b开始找最长路径的终点为d。 b, d之间的路径就是图中最长路径。证明略。粘上代码。

1 #include
     
       2  3 using namespace std; 4 struct Road 5 { 6     int d, L; 7 }; 8 vector< vector
      
        >G(11000); 9 int maxLen = 0;10 int totalLen = 0;11 int N, num;12 int  midl;13 int visited[11000]= {
    0};14 void dfs(int s)15 {16     if(num > N) return;17     for(int i=0; i
       
         maxLen)26             {27                 maxLen = totalLen;28                 midl = r.d;29             }30             dfs(r.d);31             totalLen -= r.L;32         }33     }34 }35 36 int main()37 {38     cin>> N;39     for(int i=0; i
        
         >s >> r.d >> r.L;44         G[s].push_back(r);45         Road t;46         t.d=s;47         t.L=r.L;48         G[r.d].push_back(t);49     }50     num=1;51     visited[1]=1;52     dfs(1);//任意一点开始dfs53     totalLen=0;54     maxLen=0;55     num=1;56     57     memset(visited, 0, sizeof(visited));//为重新dfs准备58     visited[midl]=1;59     dfs(midl);//上一最长路径终点开始dfs60     int a=11;61     int b=maxLen+10;62     int sum=(a+b)*maxLen/2;63     cout<< sum;64 }