SHARE
TWEET

Problem L

a guest Nov 7th, 2016 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define pb push_back
  4. #define mp make_pair
  5. #define pf printf
  6. #define sf scanf
  7. #define ins insert
  8.  
  9. #define NMax 200002
  10. using namespace std;
  11.  
  12. vector<int> addj[200010]; // declare the space needed
  13. int vis[200010],aval[200010], bval[200010], abval[200010]; // SIZE
  14.  
  15. void dfs(int a)
  16.     {  
  17.         vis[a]=-1;
  18.         for (int i = 0; i < addj[a].size(); ++i)
  19.         {
  20.             if(vis[addj[a][i]]==-1)
  21.                 continue;
  22.                
  23.             else if (vis[addj[a][i]]==0)
  24.             {
  25.                 dfs(addj[a][i]);
  26.             }
  27.             aval[a]=min(aval[a],aval[addj[a][i]]+1);
  28.             bval[a]=min(bval[a],bval[addj[a][i]]+1);
  29.             abval[a]=min(abval[a],abval[addj[a][i]]+1);
  30.         }
  31.         abval[a]=min(abval[a],aval[a]+bval[a]);
  32.         vis[a]=1;
  33.     }
  34.    
  35. int main()
  36. {
  37.     int n,m,a,b;
  38.     cin>>n>>m>>a>>b;
  39.     int y,u;
  40.     vector<int>v[n+1];
  41.    
  42.     for(int i=0;i<n+1;i++)
  43.     {
  44.         bval[i]=NMax;
  45.         aval[i]=NMax;
  46.         abval[i]=NMax;
  47.     }
  48.     aval[a]=0;
  49.     bval[b]=0;
  50.     for(int i=0;i<m;i++)
  51.     {
  52.         cin>>y>>u;
  53.         v[y].pb(u);
  54.     }
  55.    
  56.     for(int i=0;i<n+1;i++)
  57.         addj[i]=v[i];
  58.    
  59.     dfs(0);
  60.    
  61.     cout<<abval[0]<<endl;
  62.    
  63.     return 0;
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top