Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Author := Abhishek Giri
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define pb push_back]
- #define pii pair<int,int>
- #define pll pair<ll,ll>
- #define mp make_pair
- #define mod (ll)1e9 + 7
- #define V(type) vector<(type)>
- #define in(var) cin>>(var)
- #define out(var) cout<<(var)
- #define on(var) cout<<var<<"\n"
- #define f(i,n) for(ll i = 0 ; i < n ;i++)
- #define mfor(i,init,n,b) for(ll i = (init) ; i < (n) ; i+= (b))
- #define cfor(i,c) for(auto i = (c).begin() ; i!= (c).end(); i++)
- #define el "\n"
- #define ret return
- #define F first
- #define S second
- #define YES cout<<"YES\n"
- #define NO cout<<"NO\n"
- #define all(v) (v).begin(),(v).end()
- #define eps 0.00000001
- /*##################################################################################*/
- bool prime[10005] = {true};
- vector < ll > pr;
- void calculateprime()
- {
- prime[0] = prime[1] = false;
- for(int i = 2 ; i*i <= 10005 ; i++)
- {
- if(prime[i] == true)
- {
- for(ll j = i*i ; j <= 10005 ; j += i )
- {
- prime[j] = false;
- }
- }
- }
- }
- void customrun(){
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- void fast(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- ll powerwithmod(ll x, ll y, ll p = mod)
- {
- ll res = 1;
- x = x % p;
- if (x == 0) return 0;
- while (y > 0)
- {
- if (y & 1)
- res = (res*x) % p;
- y = y>>1; // y = y/2
- x = (x*x) % p;
- }
- return res;
- }
- void solve();
- int main() {
- clock_t begin = clock();
- srand(time(0));
- fast();
- customrun();
- ll t = 1;
- // cin>>t;
- // calculateprime();
- mfor(i,1,t+1,1)
- {
- // cout<<"Case #"<<i<<": ";
- solve();
- }
- clock_t end = clock();
- double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
- // cout<<"\ntime spent is "<<time_spent;
- return 0;
- }
- void solve(){
- ll v, e;
- cin>>v>>e;
- vector<vector< pair<ll,ll> > > g(v);
- for(int i = 0 ; i < e ; i++){
- ll a,b;
- cin>>a>>b;
- --a;
- --b;
- g[a].push_back({b, 1});
- g[b].push_back({a, -1});
- }
- ll s, d;
- cin>>s>>d;
- --s;--d;
- vector<pair<ll,ll> > dis(v, {INT_MAX, 10});
- vector<bool> used(v, false);
- priority_queue<pll, vector<pll>, greater<pll> > pq;
- pq.push({0,s});
- dis[s] = {0,0};
- // cout<<"hello";
- while(!pq.empty()){
- ll nxt = pq.top().second;
- ll dnxt = pq.top().first;
- pq.pop();
- if(dnxt != dis[nxt].first) continue;
- if(dis[nxt].first == INT_MAX) break;
- for(auto &i : g[nxt]){
- ll to = i.first;
- ll dir = i.second;
- if(dis[to].first > dis[nxt].first + ( dis[nxt].second + dir == 0 ) ){
- dis[to].first = dis[nxt].first + ( dis[nxt].second + dir == 0 );
- dis[to].second = dir;
- pq.push({dis[to].first, to});
- }
- }
- }
- // for(auto i : dis) cout<<i.first<<" "<<i.second<<endl;
- cout<< dis[d].first;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement