fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pii pair<int,int>
  3. #define infinity 99999999999
  4. using namespace std;
  5.  
  6.  long int n,m,u,v,w;
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13. void dijkstra(int start, vector<pii>G[])
  14.  {
  15.      long int *dist = new long int[n+1];
  16.  
  17.      priority_queue<pii,vector<pii>,greater<pii> >q;
  18.  
  19.      for(int i=1; i<=n; i++)
  20.      {
  21.         dist[i]=infinity;
  22.      }
  23.  
  24.      q.push(pii(0,start));
  25.      dist[start]=0;
  26.  
  27.      while(!q.empty())
  28.      {
  29.         u=q.top().second;
  30.         q.pop();
  31.         for(int i=0; i<G[u].size();i++)
  32.         {
  33.             v=G[u][i].second;
  34.             w=G[u][i].first;
  35.             if(dist[u]+w<dist[v])
  36.             {
  37.                 dist[v]=dist[u]+w;
  38.                 q.push(pii(dist[v],v));
  39.             }
  40.         }
  41.      }
  42.  
  43.     long int mx  = 0;
  44.     for(int i=1; i<=n; i++)
  45.     {
  46.         mx = max(mx, dist[i]);
  47.     }
  48.     cout<<mx<<endl;
  49.     free(dist);
  50.  }
  51.  
  52.  
  53.  
  54.  
  55.  
  56. int main()
  57. {
  58.      ios::sync_with_stdio(false);
  59.      cin>>n>>m;
  60.      vector<pii>G[n+1];
  61.      while(m--)
  62.      {
  63.         cin>>u>>v>>w;
  64.         G[u].push_back(pii(w,v));
  65.         G[v].push_back(pii(w,u));
  66.      }
  67.  
  68.      int start = 1;
  69.      dijkstra(start,G);
  70.  
  71.      return 0;
  72.  
  73. }
  74.  
Success #stdin #stdout 0s 16064KB
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/IoknMd
language:
C++14 (gcc 8.3)
created:
7 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!