fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ii pair<int, int>
  4. #define inf 10000000
  5. vector<int> dist;
  6. void Djikstra(vector<vector<ii> > &graph, int src){
  7. 	set <ii> S;
  8. 	S.insert({0, src});
  9. 	dist[src] = 0;
  10. 	while(!S.empty()){
  11. 		int u = S.begin()->second;
  12. 		S.erase(S.begin());
  13. 		for(auto it : graph[u]){
  14. 			int v = it.first, d = it.second;
  15. 			if(dist[v] > dist[u] + d){
  16. 				if(dist[v] != inf){
  17. 					S.erase(S.find({dist[v], v}));
  18. 				}
  19. 				dist[v] = dist[u] + d;
  20. 				S.insert({dist[v], v});
  21. 			}
  22. 		}
  23. 	}
  24. }
  25.  
  26. int main(void){
  27. 	ios::sync_with_stdio(0); cin.tie(0);
  28. 	int c, f;
  29. 	cin >> c >> f;
  30. 	vector<vector<ii> > graph(c+1, vector<ii>(0));
  31. 	while(f--){
  32. 		int x, y, w;
  33. 		cin >> x >> y >> w;
  34. 		graph[x].push_back({y, w});
  35. 		graph[y].push_back({x, w});
  36. 	}
  37. 	int ans = 0;
  38. 	for(int i = 1; i <= c; i++){
  39. 		dist.clear(); dist.resize(c+1, inf);
  40. 		Djikstra(graph, i);
  41. 		for(int j = 1; j <= c; j++){
  42. 			if(dist[j] != inf){
  43. 				ans = max(ans, dist[j]);
  44. 			}
  45. 		}
  46. 	}
  47. 	cout << ans << '\n';
  48. }
  49.  
Runtime error #stdin #stdout #stderr 0s 4436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/iaKU8P
language:
C++14 (gcc 8.3)
created:
8 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!