Advertisement
abhishekgiri219

Untitled

May 4th, 2022
314
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1. // Author := Abhishek Giri
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define pb push_back]
  7. #define pii pair<int,int>
  8. #define pll pair<ll,ll>
  9. #define mp make_pair
  10. #define mod (ll)1e9 + 7
  11. #define V(type) vector<(type)>
  12. #define in(var) cin>>(var)
  13. #define out(var) cout<<(var)
  14. #define on(var) cout<<var<<"\n"
  15. #define f(i,n) for(ll i = 0 ; i < n ;i++)
  16. #define mfor(i,init,n,b) for(ll i = (init) ; i < (n) ; i+= (b))
  17. #define cfor(i,c) for(auto i = (c).begin() ; i!= (c).end(); i++)
  18. #define el "\n"
  19. #define ret return
  20. #define F first
  21. #define S second
  22. #define YES cout<<"YES\n"
  23. #define NO cout<<"NO\n"
  24. #define all(v) (v).begin(),(v).end()
  25. #define eps 0.00000001
  26.  
  27. /*##################################################################################*/
  28.  
  29.  
  30. bool prime[10005] = {true};
  31. vector < ll > pr;
  32. void calculateprime()
  33. {
  34.     prime[0] = prime[1] = false;
  35.     for(int i = 2 ; i*i <= 10005 ; i++)
  36.     {
  37.         if(prime[i] == true)
  38.         {
  39.             for(ll j = i*i ; j <= 10005 ; j += i )
  40.             {
  41.                 prime[j] = false;
  42.             }
  43.         }
  44.     }
  45. }
  46.  
  47.  
  48.  
  49. void customrun(){
  50.     #ifndef ONLINE_JUDGE
  51.         freopen("input.txt", "r", stdin);
  52.         freopen("output.txt", "w", stdout);
  53.     #endif
  54. }
  55.  
  56. void fast(){
  57.     ios_base::sync_with_stdio(false);
  58.     cin.tie(NULL);
  59.     cout.tie(NULL);
  60. }
  61.  
  62. ll powerwithmod(ll x, ll y, ll p = mod)
  63. {
  64.     ll res = 1;
  65.  
  66.     x = x % p;
  67.  
  68.     if (x == 0) return 0;
  69.  
  70.     while (y > 0)
  71.     {
  72.         if (y & 1)
  73.             res = (res*x) % p;
  74.  
  75.         y = y>>1; // y = y/2
  76.         x = (x*x) % p;
  77.     }
  78.  
  79.     return res;
  80. }
  81.  
  82. void solve();
  83.  
  84.  
  85. int main() {
  86.     clock_t begin = clock();
  87.     srand(time(0));
  88.     fast();
  89.  
  90.     customrun();
  91.  
  92.     ll t = 1;
  93.     // cin>>t;
  94.     // calculateprime();
  95.  
  96.     mfor(i,1,t+1,1)
  97.     {
  98.         // cout<<"Case #"<<i<<": ";
  99.  
  100.         solve();
  101.     }
  102.     clock_t end = clock();
  103.     double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  104.     // cout<<"\ntime spent is "<<time_spent;
  105.     return 0;
  106. }
  107.  
  108. void solve(){
  109.     ll v, e;
  110.     cin>>v>>e;
  111.  
  112.     vector<vector< pair<ll,ll> > > g(v);
  113.  
  114.     for(int i = 0 ; i < e ; i++){
  115.         ll a,b;
  116.         cin>>a>>b;
  117.  
  118.         --a;
  119.         --b;
  120.  
  121.  
  122.         g[a].push_back({b, 1});
  123.         g[b].push_back({a, -1});
  124.     }
  125.  
  126.     ll s, d;
  127.     cin>>s>>d;
  128.     --s;--d;
  129.  
  130.     vector<pair<ll,ll> > dis(v, {INT_MAX, 10});
  131.     vector<bool> used(v, false);
  132.     priority_queue<pll, vector<pll>, greater<pll> > pq;
  133.  
  134.     pq.push({0,s});
  135.     dis[s] = {0,0};
  136.  
  137.     // cout<<"hello";
  138.  
  139.     while(!pq.empty()){
  140.         ll nxt = pq.top().second;
  141.         ll dnxt = pq.top().first;
  142.         pq.pop();
  143.  
  144.         if(dnxt != dis[nxt].first) continue;
  145.  
  146.         if(dis[nxt].first == INT_MAX) break;
  147.  
  148.         for(auto &i : g[nxt]){
  149.             ll to = i.first;
  150.             ll dir = i.second;
  151.  
  152.             if(dis[to].first > dis[nxt].first + ( dis[nxt].second + dir == 0 ) ){
  153.                 dis[to].first = dis[nxt].first + ( dis[nxt].second + dir == 0 );
  154.                 dis[to].second = dir;
  155.  
  156.                 pq.push({dis[to].first, to});
  157.             }
  158.         }
  159.     }
  160.  
  161.     // for(auto i : dis) cout<<i.first<<" "<<i.second<<endl;
  162.  
  163.     cout<< dis[d].first;
  164. }
  165.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement