fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef vector<vector<pair<int,int> > > vvpii;
  4. vvpii graph;
  5. vector<int> d;
  6. int V, E;
  7. bool comp(int a, int b)
  8. {
  9. 	return d[a] > d[b]; 
  10. }
  11. void dijkstra(int src)
  12. {
  13. 	vector<int> v(V);
  14. 	for (int i = 0; i < V; ++i)
  15. 	{
  16. 		v[i] = i;
  17. 	}
  18. 	d = vector<int>(V,INT_MAX);
  19. 	d[src] = 0;
  20. 	make_heap(v.begin(),v.end(),comp);
  21. 	int ctr = V-1;
  22. 	while (ctr--)
  23. 	{
  24. 		pop_heap(v.begin(), v.end(), comp);
  25. 		int u = v.back(); v.pop_back();
  26. 		//cout<<"u = "<<u<<endl;
  27. 		for (int i = 0; i < graph[u].size(); ++i)
  28. 		{
  29. 			pair<int,int> a = graph[u][i];
  30. 		//	cout<<"Access el "<<a.first<<"\n";
  31. 			if (d[a.first] > d[u] + a.second)
  32. 				d[a.first] = d[u] + a.second;
  33. 		}
  34. 		make_heap(v.begin(),v.end(),comp);
  35. 		/*cout<<"d[] mapp \n";
  36. 		for (int i = 0; i < V; ++i)
  37. 		{
  38. 			cout<<i<<" = "<<d[i]<<endl;
  39. 		}*/
  40. 	}
  41. }
  42. int main()
  43. {
  44. 	cin>>V;
  45. 	//Consider working with undirected here.
  46. 	graph = vvpii(V);
  47.  
  48. 	cin>>E;
  49. 	for (int i = 0; i < E; ++i)
  50. 	{
  51. 		///cout<<"hye";
  52. 		int a,b,w;
  53. 		cin>>a>>b>>w;
  54. 		graph[a-1].push_back(make_pair(b-1,w));
  55. 		graph[b-1].push_back(make_pair(a-1,w));
  56. 	}
  57. 	long maxi = 0;
  58. 	for (int i = 0; i < V; ++i)
  59. 	{
  60. 		dijkstra(i);
  61. 		for (int j = 0; j < V; ++j)
  62. 		{
  63. 			if (d[j] != INT_MAX)
  64. 			{
  65. 				if (d[j] > maxi)
  66. 					maxi = d[j];
  67. 			}
  68. 		}
  69. 	}
  70. 	cout<<maxi;
  71. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
4 5
1 2 10
1 3 24
2 3 2
2 4 15
3 4 7
stdout
copy 
19
https://ideone.com/WpDpiX
language:
C++14 (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!