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 dist1[sz],N;  //initializing distance of each node infinity
  10. int dist2[sz];
  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.     dist1[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(dist1[u]+weight_u_v<dist1[v]){
  21.                     dist1[v]=(dist1[u]+weight_u_v);
  22.                     pq.push(make_pair(dist1[v],v));
  23.                 }
  24.         }
  25.     }
  26. }
  27. void ddijkstra(int s){
  28.     priority_queue<pii, vector<pii>, greater<pii> >pq;
  29.     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
  30.     dist2[s]=0;
  31.     while(!pq.empty()){
  32.         pii top=pq.top(); pq.pop();
  33.         int d=top.first; int u=top.second;
  34.             for(it=v[u].begin();it!=v[u].end();++it){
  35.                 int v=it->first; int weight_u_v=it->second;
  36.                 if(dist2[u]+weight_u_v<dist2[v]){
  37.                     dist2[v]=(dist2[u]+weight_u_v);
  38.                     pq.push(make_pair(dist2[v],v));
  39.                 }
  40.         }
  41.     }
  42. }
  43. int main()
  44. {
  45.     int N,E,s,t,i,j,x,y,w,tc,cs=0,d;
  46.     scanf("%d",&tc);
  47.     while(tc--){
  48.     scanf("%d%d",&N,&E);
  49.     for(int i=0;i<=N;i++)dist1[i]=inf;
  50.     for(int i=0;i<=N;i++)dist2[i]=inf;
  51.     for(i=0;i<E;i++){
  52.         scanf("%d%d",&x,&y);
  53.         w=1;
  54.         v[x].push_back(make_pair(y,w));
  55.         v[y].push_back(make_pair(x,w));
  56.     }
  57.     scanf("%d%d",&s,&d);
  58.     dijkstra(s);
  59.     ddijkstra(d);
  60.     //for(i=0;i<N;i++)cout<<dist1[i]<<' ';cout<<endl;
  61.     //for(i=0;i<N;i++)cout<<dist2[i]<<' ';cout<<endl;
  62.     int mx=-1;
  63.     for(i=0;i<N;i++)mx=max(mx,dist1[i]+dist2[i]);
  64.     printf("Case %d: %d\n",++cs,mx);
  65.     for(int f=0;f<=N;f++)v[f].clear();
  66.     }
  67.     return 0;
  68. }
  69.  
  70.  
  71.  
  72.  
Time limit exceeded #stdin #stdout 5s 543744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZnPqLk
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!