fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. #define mp make_pair 
  4. #define pb push_back 
  5. #define F first 
  6. #define S second 
  7. #define f(i,n) for(int i=0;i<n;i++) 
  8. #define fr(i,a,b) for(int i=a;i<b;i++) 
  9.  
  10. using namespace std;
  11.  
  12. void dijkstra(ll dist[],set<pair<ll,ll> > st,vector<pair<ll,ll> > adj[],int n){
  13. 	while(!st.empty()){
  14. 		auto it = st.begin();
  15. 		pair<ll,ll> p = (*it);
  16. 		st.erase(it);
  17. 		ll dis = p.F;
  18. 		ll x = p.S;
  19. 		// cout<<x<<"--\n";
  20. 		f(j,adj[x].size()){
  21. 			int ver = adj[x][j].F;
  22. 			int dis2 = adj[x][j].S;
  23. 			if(dist[ver]>dis+dis2){
  24. 				// cout<<"yo yo \n";
  25. 				it = st.find({dist[ver],ver});
  26. 				st.erase(it);
  27. 				dist[ver]=dis+dis2;
  28. 				st.insert({dis+dis2,ver});
  29. 			}
  30. 		}
  31. 	}
  32. }
  33.  
  34. ll distant[2002][2002];
  35.  
  36. ll graph[2002][2002];
  37.  
  38. void test(){
  39. 	int n,m;
  40. 	cin>>n>>m;
  41. 	vector<pair<ll,ll> > adj[n+1];
  42. 	memset(graph,-1,sizeof(graph));
  43. 	memset(distant,-1,sizeof(distant));
  44. 	f(i,m){
  45. 		ll u,v,w;
  46. 		cin>>u>>v>>w;
  47. 		if(graph[u][v]!=-1){
  48. 			if(graph[u][v]>w){
  49. 				graph[u][v] = w;
  50. 			}
  51. 		}else
  52. 			graph[u][v] = w;
  53. 	}
  54.  
  55. 	f(i,n+1){
  56. 		f(j,n+1){
  57. 			if(i!=j){
  58. 				if(graph[i][j]!=-1){
  59. 					adj[i].pb({j,graph[i][j]});
  60. 				}
  61. 			}
  62. 		}
  63. 	}
  64.  
  65. 	ll max_dis = 1000000000000 ;
  66.  
  67. 	for(int i=1;i<=n;i++){
  68. 		ll dist[n+1];
  69. 		f(j,n+1)dist[j]=max_dis;
  70. 		dist[i] = 0;
  71. 		set<pair<ll,ll> >  st;
  72. 		fr(j,1,n+1){
  73. 			st.insert({dist[j],j});
  74. 		}
  75. 		dijkstra(dist,st,adj,n);
  76. 		for(int j=1;j<=n;j++){
  77. 			if(j!=i and dist[j]!=max_dis){
  78. 				distant[i][j] = dist[j];
  79. 			}
  80. 		}
  81. 		if(graph[i][i]!=-1)distant[i][i] = graph[i][i];
  82. 	}
  83.  
  84.  
  85. 	vector<ll> sol;
  86. 	for(int i=1;i<=n;i++){
  87. 		ll res = max_dis*2LL;
  88. 		for(int j=1;j<=n;j++){
  89. 			if(distant[i][j]!=-1 and distant[j][i]!=-1){
  90. 				if(i==j)res = min(res,distant[i][j]);
  91. 				else res = min(res, distant[i][j] + distant[j][i]);
  92. 			}
  93. 		}
  94. 		if(res==(max_dis*2LL))
  95. 			res = -1;
  96. 		sol.pb(res);
  97. 	}
  98. 	for(auto p : sol)cout<<p<<"\n";
  99.  
  100. }
  101.  
  102. int main(){
  103. 	int t=1;
  104. //	cin>>t;
  105. 	while(t--){
  106. 		test();
  107. 	}
  108. }
  109.  
Runtime error #stdin #stdout 0s 4864KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/LAUVaK
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!