fork download
copy 
  1. #include <iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<set>
  5. #include<map>
  6.  
  7. using namespace std;
  8.  
  9. #define max 100001
  10.  
  11. map<int,bool>visit;
  12. map<int,int> revcnt;
  13. vector<int> v[max];
  14. set<int> s[max];
  15.  
  16. int main()
  17. {
  18.     int n,edges,i,c;
  19.     cin>>n>>edges;
  20.     for(i=0;i<=n;i++)
  21.      {
  22.          visit[i]=0;
  23.          revcnt[i]=max;
  24.          v[i].clear();
  25.      }
  26.      int x,y;
  27.  
  28.      while(edges--)
  29.      {
  30.          cin>>x>>y;
  31.          s[x].insert(y);
  32.          v[x].push_back(y);
  33.          v[y].push_back(x);
  34.      }
  35.  
  36.      priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
  37.  
  38.      Q.push(make_pair(0,1));
  39.      visit[1]=0;
  40.      revcnt[1]=0;
  41.  
  42.      while(!Q.empty())
  43.      {
  44.          pair<int,int> p=Q.top();
  45.          Q.pop();
  46.          if(!visit[p.second])
  47.          {
  48.              visit[p.second]=1;
  49.              if(p.second==n)
  50.              {
  51.                  cout<<p.first<<endl;
  52.                  break;
  53.              }
  54.              else
  55.              {
  56.                  for(int i=0;i<(int)v[p.second].size(); i++)
  57.                  {
  58.                      int key=v[p.second][i];
  59.                      if(!visit[key])
  60.                      {
  61.                          if(s[p.second].find(key)!=s[p.second].end())
  62.                          {
  63.                              c=p.first+0; // i.e. an edge already exists
  64.                              if(c<revcnt[key])
  65.                              revcnt[key]=c;
  66.                          }
  67.                          else
  68.                          {
  69.                              c=p.first+1; // i.e. we need to reverse an edge
  70.                              if(c<revcnt[key])
  71.                              revcnt[key]=c;
  72.                          }
  73.                          Q.push(make_pair(revcnt[key],key));
  74.                      }
  75.                  }
  76.              }
  77.          }
  78.      }
  79.  
  80.      if(revcnt[n]==max)
  81.      cout<<"-1"<<endl;
  82.      //else
  83.      //cout<<revcnt[n]<<endl;
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 7000KB
comments (?)
stdin
copy 
4 4
2 1
3 2
4 3
4 1
stdout
copy 
1
https://ideone.com/IeMIdK
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!