fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() 
  6. {
  7. 	ios::sync_with_stdio(0);
  8. 	int C,F,a,b; long long cost;
  9. 	cin>>C>>F;
  10. 	vector<pair<int,int>> flights[C+1];
  11. 	for(int i=0; i<F; i++)
  12. 	{
  13. 	    cin>>a>>b>>cost;
  14. 	    flights[a].push_back(make_pair(cost,b));
  15. 	    flights[b].push_back(make_pair(cost,a));
  16. 	}
  17. 	for(int i=1; i<=C; i++)
  18. 	{
  19. 	    sort(flights[i].begin(), flights[i].end());
  20. 	}
  21. 	long long int mincost[C+1][C+1];
  22. 	for(int i=1; i<=C; i++)
  23. 	{
  24. 	    for(int j=1; j<=C; j++)
  25. 	    {
  26. 	        mincost[i][j]=LLONG_MAX;
  27. 	    }
  28. 	}
  29. 	for(int i=1; i<=C; i++)
  30. 	{
  31. 	    long long int cost[C+1];
  32. 	    for(int j=1; j<=C; j++)
  33. 	    {
  34. 	        cost[j]=LLONG_MAX;
  35. 	    }
  36. 	    cost[i]=0;
  37. 	    priority_queue<pair<int,int>> Q;
  38. 	    Q.push(make_pair(0,i));
  39. 	    while(!Q.empty())
  40. 	    {
  41. 	        int X=Q.top().second;
  42. 	        Q.pop();
  43. 	        for(int j=0; j<flights[X].size(); j++)
  44. 	        {
  45. 	            int tcost=flights[X][j].first, idx=flights[X][j].second;
  46. 	            if (cost[idx]>cost[X]+tcost)
  47.                 {
  48.                     cost[idx]=cost[X]+tcost;
  49.                     Q.push(make_pair(cost[idx], idx));
  50.                 }
  51.             }
  52. 	    }
  53. 	    for(int j=1; j<=C; j++)
  54. 	    {
  55. 	        if(j!=i)
  56. 	        {
  57. 	            mincost[i][j]=cost[j];
  58. 	            mincost[j][i]=cost[j];
  59. 	        }
  60. 	    }
  61.  
  62. 	}
  63. 	long long int ans=0;
  64. 	for(int i=1; i<=C; i++)
  65. 	{
  66. 	    for(int j=1; j<=C; j++)
  67. 	    {
  68. 	        //cout<<mincost[i][j]<<" ";
  69. 	        if(i!=j)
  70. 	            ans=max(ans,mincost[i][j]);
  71. 	    }
  72. 	    //cout<<endl;
  73. 	}
  74. 	cout<<ans<<endl;
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 15248KB
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/cp0xEt
language:
C++14 (clang 8.0)
created:
7 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!