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
1 7 1 2 20 2 3 10 2 4 20 4 5 10 5 6 10 4 7 40
Sample Output
80
Source: TJU Team Selection Contest 2010 (3)
解题:求树的直径。。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 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 }
相关文章
- 记录一次在生成数据库服务器上出现The timeout period elapsed prior to completion of the operation or the server is not responding.和Exception has been thrown by the target of an invocation的解决办法
- 【Https异常】This request has been blocked; the content must be served over HTTPS
- Java实现 洛谷 P6183 [USACO10MAR]The Rock Game S(DFS)
- [CSS] Specify grid columns, rows, and areas at once with the grid-template shorthand
- [NativeScript] Style NativeScript views using the default core theme
- Caused by: org.xml.sax.SAXParseException: The reference to entity "characterEncoding" must end with the ';' delimiter.
- Error: Connection lost: The server closed the connection
- [Javascript] Broadcaster + Operator + Listener pattern -- 11. Customize the done logic
- Unexpected XML declaration. The XML declaration must be the first node in the document and no white
- The data replication requires the processing of single BDoc instances
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- 【Codeforces Round #430 (Div. 2) C】Ilya And The Tree
- 【Codeforces Round #426 (Div. 2) A】The Useless Toy
- How is dependent libraries defined in metadata loaded in the runtime
- The resource could not be loaded because the App Transport Security policy requires the use of a sec
- 成功解决404 Not Found Not Found The requested URL was not found on the server. If yo
- httpd: Could not reliably determine the server's fully qualified domain name
- chroumium electron apply_all_patches.py patch git error WindowsError: [Error 2] The system cannot find the file specified
- HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树
- 【问题解决】The connection to the server localhost:8080 was refused
- macOS The bottle needs the Xcode CLT to be installed
- 解决办法:错误异常The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path
- 编译webrtc报错:ERROR: The installation of the Chrome OS default fonts failed.
- The SDK path ‘UserscmmLibraryAndroidsdk‘ does not belong to a directory. Android Studio will u