题目链接：http://soj.sysu.edu.cn/1024 这里要注意到，有n个点，但是只有n-1条路径，说明是树，用dfs求树的最长路径： （用c++输入0.35s，用c输入0.18s）
#include <iostream> #include <vector> #include <string.h> #include <cstring> #include <stdio.h> using namespace std; struct Road { int to, distance;//目的地和距离 Road(int new_to, int new_distance) {//这样写为了读入方便 to = new_to; distance = new_distance; } }; vector<Road> roads[10001];//注意这里是二维动态数组 bool vis[10001]; int longest_road, n; void dfs(int from, int dis) { if (dis > longest_road)//更新最长的路径 longest_road = dis; vis[from] = true;//这个点已经访问过，不重复访问 for (int i = 0; i < (int)roads[from].size(); i++) {//遍历from所能连通的点并判断是否dfs if (!vis[roads[from][i].to]) { dfs(roads[from][i].to, dis + roads[from][i].distance); } } } int main() { int k, i, temp_from, temp_to, new_distance; while (cin >> n >> k) { longest_road = 0; memset(vis, false, sizeof(vis)); memset(roads, 0, sizeof(roads)); for (i = 0; i < n - 1; i++) { scanf("%d%d%d", &temp_from, &temp_to, &new_distance); roads[temp_from].push_back(Road(temp_to, new_distance));//注意这里两点是互通的 roads[temp_to].push_back(Road(temp_from, new_distance)); } dfs(k, 0); printf("%d\n", longest_road); } return 0; }