fork(1) download 
  1. #include<iostream>
  2. #include<map>
  3. #include<cmath>
  4. #include<vector>
  5. #include<algorithm>
  6. #include<iomanip>
  7. #include<cmath>
  8. #include<stack>
  9. #include<math.h>
  10. #include<set>
  11. #include<string>
  12. #include<cstring>
  13. #include<queue>
  14. #include<complex>		
  15. #include<sstream>	
  16. #include<cstdio>
  17. using namespace std;
  18.  
  19. const double EPS = 1e-7;
  20. const double PI = acos(-1.0);
  21. const double ZERO = 0;
  22. const double DOUBLE_MAX = 1/ZERO;
  23. typedef complex<double> point;
  24. #define X real()
  25. #define Y imag()
  26. #define rad(p) (atan2((p.Y),(p.X)))
  27. #define dot(a,b) ((conj(a)*(b)).real())
  28. #define cross(a,b) ((conj(a)*(b)).imag())
  29. #define length(a) hypot((a).X,(a).Y)
  30. #define normalize(p) ((p)/length(p))
  31. #define rotate(p,origin,ang) (((p)-(origin))*exp(point(0,(ang)))+(origin))
  32. #define collinear(a,b,c) ( fabs( cross((a)-(b),(c)-(b))) < EPS)
  33. #define bisector(a,b) (((a)+(b))/2.0) // return the mid point
  34. #define polar(r,theta) (point((r),0)*exp(point(0,(theta))))
  35.  
  36. #define rep(i,n) for(int i=0;i<n;i++)
  37. #define repi(i,a,n) for(int i=a;i<n;i++)
  38. #define inf (0x7fffffff)
  39. #define mp make_pair
  40. #define read freopen("in.in","r",stdin)
  41. #define write freopen("out.out","w",stdout)
  42. #define scf(xx) scanf("%d",&xx)
  43. typedef  long long ll;
  44. typedef vector<int> vi;
  45. typedef pair<int,int> ii;
  46. typedef  long double ld;
  47.  
  48. vector< vector<int> > comToNode;        
  49. vector<int> nodeToCom;
  50.  
  51. vector<int> indx;               // order of each node in the DFS, initialized by -1
  52. vector<int> lowLink;    // after runing the algorithm, it has a unique indx for each component, this indx is the minimum indx for the set of nodes in that component
  53. stack<int> stk;                 // has the current nodes currently in the stack
  54. int curIndex;
  55. vector<vector<ii> > adjList;   // the graph
  56. vector<bool> inStack;   // 1 for nodes that are currently in the stack, 0 otherwise
  57.  
  58. void tarjanDFS(int i, int par) {
  59.         lowLink[i] = indx[i] = curIndex++;
  60.         stk.push(i);
  61.         inStack[i] = 1;
  62.         for(int j=0;j<adjList[i].size();j++) {
  63. 			if(indx[ adjList[i][j].first ]==-1 && adjList[i][j].first!=par) {
  64. 				tarjanDFS( adjList[i][j].first ,i );
  65. 				lowLink[i] = min(lowLink[i],lowLink[ adjList[i][j].first ]);
  66.                 }
  67. 			else if(inStack[ adjList[i][j].first ] && adjList[i][j].first!=par) 
  68. 				lowLink[i] = min(lowLink[i],indx[ adjList[i][j].first]);
  69.         }
  70.         if(indx[i] == lowLink[i])       { 
  71.                 vector<int> v;
  72.                 while(!stk.empty()) {
  73.                         int ind = stk.top();
  74.                         stk.pop();
  75.                         v.push_back(ind);                       // updating the answer
  76.                         nodeToCom[ind] = comToNode.size();      // updating the answer
  77.                         inStack[ind] = 0;       
  78.                         if(ind==i) break;
  79.                 }
  80.                 comToNode.push_back(v);                         // updating the answer
  81.         }
  82. }
  83.  
  84. void tarjanSCC(int n) {
  85.  
  86.         indx = vector<int>(n,-1);
  87.         lowLink = vector<int>(n,-1);
  88.         nodeToCom = vector<int>(n,-1);
  89.         comToNode = vector< vector<int> >();
  90.         inStack = vector<bool>(n,0);
  91.         stk = stack<int>();
  92.         curIndex = 0;
  93.  
  94.         for(int i=0;i<adjList.size();i++) 
  95.                 if(indx[i]==-1) 
  96.                         tarjanDFS(i,-1);
  97. }
  98.  
  99. int n,m;
  100. vector<vector<ii> > G;
  101. bool vis[100001];
  102. void dfs(int id){
  103. 	vis[id]=1;
  104. 	rep(i,adjList[id].size()){
  105. 		int node=adjList[id][i].first;
  106. 		if(!vis[node]){
  107. 			if(nodeToCom[id]!=nodeToCom[node]){
  108. 				G[nodeToCom[id]].push_back( mp(nodeToCom[node],adjList[id][i].second));
  109. 				G[nodeToCom[node]].push_back( mp(nodeToCom[id],adjList[id][i].second));
  110. 			}
  111. 			dfs(node);
  112. 		}
  113. 	}
  114. }
  115. int parent[100001];
  116. ll dis[100001];
  117. int F;
  118. ll ma;
  119. void dfs1(int id,int par,ll d){
  120. 	if(d>ma){ma=d; F=id;}
  121. 	dis[id]=d; parent[id]=par;
  122. 	rep(i,G[id].size()){
  123. 		if(par!=G[id][i].first)
  124. 			dfs1(G[id][i].first,id,d+G[id][i].second);
  125. 	}
  126. }
  127. int main(){
  128. 	//read;
  129. 	//write;
  130. 	int x,y,z,t; cin>>t;
  131. 	while(t--){
  132. 		cin>>n>>m;
  133. 		adjList=vector<vector<ii> >(n);
  134. 		while(m--){
  135. 			scanf("%d%d%d",&x,&y,&z);
  136. 			x--; y--;
  137. 			adjList[x].push_back(mp(y,z));
  138. 			adjList[y].push_back(mp(x,z));
  139. 		}
  140. 		tarjanSCC(n);
  141. 		rep(i,comToNode.size())sort(comToNode[i].begin(),comToNode[i].end());
  142. 		G=vector<vector<ii> >(comToNode.size());
  143. 		memset(vis,false,sizeof vis);
  144. 		dfs(0);
  145. 		//memset(parent,-1,sizeof parent);
  146. 		//memset(dis,-1,sizeof dis);
  147. 		F=0; ma=-1;
  148. 		dfs1(0,-1,0);
  149. 		ma=-1;
  150. 		int st=F;
  151. 		dfs1(F,-1,0);
  152. 		int en=F;
  153. 		int node;
  154. 		ll res=(ll)1<<60;
  155. 		ll xx;
  156. 		while(F!=-1){
  157. 			xx=max(dis[F],dis[en]-dis[F]);
  158. 			if(xx<res){ res=xx; node=comToNode[F][0];}
  159. 			else if(xx==res && node > comToNode[F][0] ) node=comToNode[F][0];
  160. 			F=parent[F];
  161. 		}
  162. 		cout<<node+1<<" "<<res<<endl;
  163. 	}
  164. }
Runtime error #stdin #stdout 0s 4704KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7bQaxz
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!