fork download
copy 
  1. //Hints:Competitive programming books by Steven & Felix Halim
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define inf 0x3f3f3f3f
  5. #define sz 123456
  6. #define pii pair<int,int>
  7. vector<pii>v[sz];
  8. vector<pii>::iterator it;
  9. int dist[sz];  //initializing distance of each node infinity
  10.  
  11. void dijkstra(int s){
  12.     priority_queue<pii, vector<pii>, greater<pii> >pq;
  13.     pq.push(make_pair(0,s));    //shorted in non-increasing order w.r.t distance so that the least distance can be pop out first
  14.     dist[s]=0;
  15.     while(!pq.empty()){
  16.         pii top=pq.top(); pq.pop();
  17.         int d=top.first; int u=top.second;
  18.             for(it=v[u].begin();it!=v[u].end();++it){
  19.                 int v=it->first; int weight_u_v=it->second;
  20.                 if(max(dist[u],weight_u_v)<dist[v]){
  21.                     dist[v]=max(dist[u],weight_u_v);
  22.                     pq.push(make_pair(dist[v],v));
  23.                 }
  24.         }
  25.     }
  26. }
  27. int main()
  28. {
  29.     int N,E,s,t,i,j,x,y,w,tc,cs=0;
  30.     scanf("%d",&tc);
  31.     while(tc--){
  32.     scanf("%d%d",&N,&E);
  33.     for(i=0;i<N;i++)dist[i]=inf;
  34.     for(i=0;i<E;i++){
  35.         scanf("%d%d%d",&x,&y,&w);
  36.         v[x].push_back(make_pair(y,w));
  37.         v[y].push_back(make_pair(x,w));
  38.     }
  39.     scanf("%d",&s);
  40.     dijkstra(s);
  41.     printf("Case %d:\n",++cs);
  42.     for(i=0;i<N;i++){
  43.         if(dist[i]==inf)printf("Impossible\n");
  44.         else printf("%d\n",dist[i]);
  45.     }
  46.     for(int f=0;f<N;f++)v[f].clear();
  47.     }
  48.     return 0;
  49. }
  50.  
  51. /*
  52. 5 6
  53. 0 1 5
  54. 0 1 4
  55. 2 1 3
  56. 3 0 7
  57. 3 4 6
  58. 3 1 8
  59. 1
  60. */
  61.  
Success #stdin #stdout 0s 18600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UYLvoi
language:
C++14 (gcc 8.3)
created:
6 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!