fork(1) download
copy 
  1. #include <iostream>
  2. #include<vector>
  3. #include<set>
  4. #include<map>
  5.  
  6. using namespace std;
  7.  
  8. #define max 100001
  9.  
  10. map<int,bool>visit;
  11. map<int,int> revcnt;
  12. vector<int> v[max];
  13. set<int> s[max];
  14. map<pair<int,int>, int> m;
  15. map<pair<int,int>, int>:: iterator it;
  16.  
  17. void dijkstra(int n)
  18. {
  19.     int i,source=1,cnt=0,key,c;
  20.     revcnt[source]=0;
  21.     m.insert(make_pair(make_pair(revcnt[source],cnt),source));
  22.     visit[source]=1;
  23.     cnt++;
  24.  
  25.     while(m.begin()!=m.end())
  26.     {
  27.         it=m.begin();
  28.         source=it->second;
  29.         visit[source]=1;
  30.         if(source==n)
  31.         {
  32.         //	f=1;
  33.         	break;
  34.         }
  35.         m.erase(it);
  36.         for(i=0;i<(int)v[source].size();i++)
  37.         {
  38.             key=v[source][i];
  39.             if(!visit[key])
  40.             {
  41.             	//cout<<" key is "<<key<<" ";
  42.                 if(s[source].find(key)!=s[source].end())
  43.                 {
  44.                     // source->v[source][i] is an edge in the graph
  45.                     c=revcnt[source];
  46.                     if(c<revcnt[key])
  47.                     revcnt[key]=c;
  48.                 }
  49.                 else
  50.                 {
  51.  
  52.                     c=revcnt[source]+1;
  53.                     //cout<<"c is "<<c<<endl;
  54.                     if(c<revcnt[key])
  55.                     revcnt[key]=c;
  56.                 }
  57.                 //cout<<" for k as "<<key<<" "<<revcnt[key]<<endl;
  58.                 m.insert(make_pair(make_pair(revcnt[key],cnt),key));
  59.                 cnt++;
  60.                 //visit[key]=1;
  61.             }
  62.         }
  63.  
  64.     }
  65. }
  66.  
  67. int main()
  68. {
  69.     int n,edges,i;
  70.     cin>>n>>edges;
  71.     for(i=0;i<=n;i++)
  72.      {
  73.          visit[i]=0;
  74.          revcnt[i]=max;
  75.          v[i].clear();
  76.      }
  77.      int x,y;
  78.  
  79.      while(edges--)
  80.      {
  81.          cin>>x>>y;
  82.          s[x].insert(y);
  83.          v[x].push_back(y);
  84.          v[y].push_back(x);
  85.  
  86.      }
  87.  
  88.      dijkstra(n);
  89.  
  90.      if(!visit[n])
  91.      cout<<"-1"<<endl;
  92.      else
  93.      cout<<revcnt[n]<<endl;
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 6956KB
comments (?)
stdin
copy 
6 6
1 2
2 3
4 3
5 4
6 5
1 6
stdout
copy 
0
https://ideone.com/7347aF
language:
C++ (gcc 8.3)
created:
9 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!