fork download
copy 
  1. /*
  2.    Mayank Pratap Singh
  3.    MNNIT, 2nd year IT
  4.    AC ho.
  5. */
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define ff first
  9. #define ss second
  10. #define pb push_back
  11. #define mp make_pair
  12.  
  13. #define MOD 1000000007
  14.  
  15. typedef long long ll;
  16. typedef long double ld;
  17.  
  18. const int INF=(int)(1e9);
  19. const ll INF64=(ll)(1e18);
  20. const ld EPS=1e-9;
  21. const ld PI=3.1415926535897932384626433832795;
  22.  
  23.  
  24. typedef vector<int> vi;
  25. typedef vector<pair<int,int> > vii;
  26. typedef vector<list<int> > vl;
  27. typedef vector<list<pair<int,int> > > vlp;
  28. typedef map<int,int> mi;
  29. typedef map<string,int> ms;
  30. typedef set<int> si;
  31.  
  32. vl adjList(10005);
  33. int n,m;
  34. map<pair<int,int>,int>slope; // Tells whether uphill or downhill
  35.  
  36. int parent[10005];
  37. int level[10005];
  38. int gearchanges[10005];   // Stores the number of gear mode changes till vertex i
  39.  
  40. int howArrived[10005];   // Stores whether we have arrived at a vertex i using uphill or downhill
  41.  
  42. void bfs(int start){
  43.  
  44.    for(int i=1;i<=n;++i){
  45.  
  46.         level[i]=-1;
  47.         howArrived[i]=-1;
  48.    }
  49.  
  50.    level[start]=0;
  51.    queue<int>VertexQueue; // Queue for implementation of bfs
  52.  
  53.    VertexQueue.push(start);
  54.  
  55.    list<int>::iterator it;
  56.  
  57.    while(!VertexQueue.empty()){
  58.  
  59.        int newVertex=VertexQueue.front();
  60.  
  61.        VertexQueue.pop();
  62.  
  63.        if(newVertex==start){
  64.  
  65.           for(it=adjList[newVertex].begin();it!=adjList[newVertex].end();++it){
  66.  
  67.                if(level[*it]==-1){
  68.  
  69.                     if(slope[mp(newVertex,*it)]==0)
  70.                         howArrived[*it]=0;
  71.                     else
  72.                         howArrived[*it]=1;
  73.  
  74.                     gearchanges[*it]=0;
  75.  
  76.                     level[*it]=level[newVertex]+1;
  77.  
  78.                     VertexQueue.push(*it);
  79.                }
  80.           }
  81.  
  82.        }
  83.  
  84.        else{
  85.  
  86.           for(it=adjList[newVertex].begin();it!=adjList[newVertex].end();++it){
  87.  
  88.               if(level[*it]==-1){
  89.  
  90.                    if(slope[mp(newVertex,*it)]==0)
  91.                        howArrived[*it]=0;
  92.                    else
  93.                        howArrived[*it]=1;
  94.  
  95.                     if(howArrived[*it]!=howArrived[newVertex])
  96.                       gearchanges[*it]=gearchanges[newVertex]+1;
  97.                     else
  98.                       gearchanges[*it]=gearchanges[newVertex];
  99.  
  100.                     level[*it]=level[newVertex]+1;
  101.  
  102.                     VertexQueue.push(*it);
  103.  
  104.               }
  105.  
  106.               else{
  107.  
  108.                   if(slope[mp(newVertex,*it)]==0){
  109.  
  110.                       if(slope[mp(newVertex,*it)]!=howArrived[newVertex]){
  111.  
  112.                           if(gearchanges[*it]>gearchanges[newVertex]+1){
  113.                               gearchanges[*it]=gearchanges[newVertex]+1;
  114.                               howArrived[*it]=0;
  115.                               level[*it]=level[newVertex]+1;
  116.                           }
  117.  
  118.                       }
  119.  
  120.                       else{
  121.  
  122.                          if(gearchanges[*it]>gearchanges[newVertex]){
  123.                             gearchanges[*it]=gearchanges[newVertex];
  124.                             howArrived[*it]=0;
  125.                             level[*it]=level[newVertex]+1;
  126.                          }
  127.  
  128.                       }
  129.  
  130.  
  131.                   }
  132.  
  133.                   else if(slope[mp(newVertex,*it)]==1){
  134.  
  135.                       if(slope[mp(newVertex,*it)]!=howArrived[newVertex]){
  136.  
  137.                           if(gearchanges[*it]>gearchanges[newVertex]+1){
  138.                               gearchanges[*it]=gearchanges[newVertex]+1;
  139.                               howArrived[*it]=1;
  140.                               level[*it]=level[newVertex]+1;
  141.                           }
  142.  
  143.                       }
  144.  
  145.                       else{
  146.  
  147.                          if(gearchanges[*it]>gearchanges[newVertex]){
  148.                             gearchanges[*it]=gearchanges[newVertex];
  149.                             howArrived[*it]=1;
  150.                             level[*it]=level[newVertex]+1;
  151.                          }
  152.  
  153.                       }
  154.  
  155.  
  156.                   }
  157.               }
  158.           }
  159.  
  160.        }
  161.    }
  162.  
  163. }
  164.  
  165.  
  166. int main(){
  167.  
  168.     int u,v;
  169.     scanf("%d %d",&n,&m);
  170.  
  171.     for(int i=1;i<=m;++i){
  172.  
  173.         scanf("%d %d",&u,&v);
  174.         adjList[u].pb(v);
  175.         adjList[v].pb(u);
  176.         slope[mp(u,v)]=0;  // Downhill
  177.         slope[mp(v,u)]=1;  // uphill
  178.     }
  179.  
  180.     int start,end;
  181.     scanf("%d %d",&start,&end);
  182.  
  183.     bfs(start);
  184.  
  185.     printf("%d\n",gearchanges[end]);
  186.  
  187.  
  188.  
  189.     return 0;
  190. }
  191.  
Runtime error #stdin #stdout 0s 3576KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iLeGnr
language:
C++14 (clang 8.0)
created:
8 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!