This is the problem to find the tree diameter.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <iostream> #include <fstream> #include <sstream> #include <map> #include <vector> #include <string> #include <queue> #include <string.h> #include <stdio.h> #define ull unsigned long long #define SZ 10002 #define FOR(i,a) for(int i=0;i<a;i++) using namespace std; vector<int> graph[SZ]; bool visit[SZ]; int distnce[SZ][SZ]; ull distnode[SZ]; ull max_dist=0; int farthestnode; void bfs(int u) { int tmp; memset(visit,0,sizeof(visit)); int next_node; max_dist=0; queue<int> q; q.push(u); distnode[u]=0; while(!q.empty()) { tmp = q.front(); q.pop(); visit[tmp]=1; if(distnode[tmp]>max_dist) { max_dist=distnode[tmp]; farthestnode = tmp; } for(int i=0;i<graph[tmp].size();i++) { next_node = graph[tmp][i]; if(!visit[next_node]) { distnode[next_node]=distnode[tmp]+distnce[tmp][next_node]; q.push(next_node); } } } } int main() { string s,s1; int from,dest,cost; stringstream ss; while(!cin.eof()) { getline(cin,s); if(s=="") { cout<<0<<"\n"; continue; } FOR(i,SZ) graph[i].clear(); memset(distnce,0,sizeof(distnce)); memset(distnode,0,sizeof(distnode)); while(!cin.eof() && s.size()>0) { if(s=="") break; ss.clear(); ss<<s; ss>>from>>dest>>cost; graph[from].push_back(dest); graph[dest].push_back(from); distnce[from][dest]=cost; distnce[dest][from]=cost; getline(cin,s); } bfs(1); bfs(farthestnode); cout<<max_dist<<"\n"; } return 0; } |