首页 > 代码库 > TOJ 3517 The longest athletic track
TOJ 3517 The longest athletic track
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 880 Accepted Runs: 342
After a long time of algorithm training, we want to hold a running contest in our beautiful campus. Because all of us are curious about a coders‘s fierce athletic contest,so we would like a more longer athletic track so that our contest can last more .
In this problem, you can think our campus consists of some vertexes connected by roads which are undirected and make no circles, all pairs of the vertexes in our campus are connected by roads directly or indirectly, so it seems like a tree, ha ha.
We need you write a program to find out the longest athletic track in our campus. our athletic track may consist of several roads but it can‘t use one road more than once.
Input
*Line 1: A single integer: T represent the case number T <= 10
For each case
*Line1: N the number of vertexes in our campus 10 <= N <= 2000
*Line2~N three integers a, b, c represent there is a road between vertex a and vertex b with c meters long
1<= a,b <= N, 1<= c <= 1000;
Output
For each case only one integer represent the longest athletic track‘s length
Sample Input
171 2 202 3 102 4 204 5 105 6 104 7 40
Sample Output
80
Source: TJU Team Selection Contest 2010 (3)
解题：求树的直径。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 2010;18 struct arc{19 int to,w,next;20 arc(int x = 0,int y = 0,int z = -1){21 to = x;22 w = y;23 next = z;24 }25 };26 arc e[maxn*20];27 int head[maxn],d[maxn],tu,tot,n;28 void add(int u,int v,int w){29 e[tot] = arc(v,w,head[u]);30 head[u] = tot++;31 e[tot] = arc(u,w,head[v]);32 head[v] = tot++;33 }34 int bfs(int u){35 queue<int>q;36 memset(d,-1,sizeof(d));37 q.push(u);38 d[u] = 0;39 int maxlen = 0;40 while(!q.empty()){41 u = q.front();42 q.pop();43 if(d[u] > maxlen) maxlen = d[tu = u];44 for(int i = head[u]; ~i; i = e[i].next){45 if(d[e[i].to] > -1) continue;46 d[e[i].to] = d[u] + e[i].w;47 q.push(e[i].to);48 }49 }50 return maxlen;51 }52 int main() {53 int T,u,v,w;54 scanf("%d",&T);55 while(T--){56 scanf("%d",&n);57 memset(head,-1,sizeof(head));58 for(int i = tot = 0; i+1 < n; ++i){59 scanf("%d %d %d",&u,&v,&w);60 add(u,v,w);61 }62 bfs(1);63 printf("%d\n",bfs(tu));64 }65 return 0;66 }
TOJ 3517 The longest athletic track