UVA10308Roads in the North(dfs)

UVA10308Roads in the North(dfs)

题目链接

题目大意：给你多条道路，每条道路都连着两个不同的城市，并且给你这条路的距离，现在要求你找出离得最远的两个城市之间的距离。

解题思路：一开始，想用dfs，可是没有想到只需要任意找个节点dfs一次就可以了，还想着如果每个点都找一次，那么肯定行不通。看了题解后才发现只需要找一次就可以了，因为题目给的是一棵树，而且两个节点之间的距离可以通过dfs来得到，只要在过程中记录下最大值就可以。

代码:

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 10005; int vis[maxn]; int ans; struct node { int id, val; node (int id = 0, int val = 0) { this->id = id; this->val = val; } }; vector
       
         v[maxn]; int dfs (int r) { int num = 0; int n = v[r].size(); vis[r] = 1; for (int i = 0; i < n; i++) if (!vis[v[r][i].id]) { int tmp = dfs(v[r][i].id) + v[r][i].val; ans = max (ans, tmp + num); num = max (num, tmp); } vis[r] = 0; return num; } int main () { char str[1000]; int a, b, val; while (true) { ans = 0; for (int i = 1; i <= maxn - 5; i++) v[i].clear(); while (gets(str) != NULL && str[0] != '\0') { sscanf (str, "%d%d%d", &a, &b, &val); v[a].push_back(node(b, val)); v[b].push_back(node(a, val)); } dfs(1); printf ("%d\n", ans); if (str[0] != '\0') break; } return 0; }