Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Giorgi Kldiashvili
- #include <bits/stdc++.h>
- #define ll long long
- #define M 1234567LL
- using namespace std;
- priority_queue < pair < int, int > > q;
- int n, m, st, en;
- vector < pair < int, int > > G[200020];
- int D[200020];
- void go(int v)
- {
- for(int i = 0; i < G[v].size(); ++ i)
- {
- int to = G[v][i].first;
- if(D[to] > D[v] + G[v][i].second)
- {
- D[to] = D[v] + G[v][i].second;
- q.push(make_pair(- D[to], to));
- }
- }
- while(!q.empty())
- {
- int x = q.top().second;
- int y = -q.top().first;
- q.pop();
- if(D[x] == y)
- go(x);
- }
- }
- int main()
- {
- scanf("%d %d %d %d", &n, &m, &st, &en);
- for(int i = 0; i < m; ++ i)
- {
- int x, y;
- scanf("%d %d", &x, &y);
- G[x].push_back(make_pair(y, 0));
- G[y].push_back(make_pair(x, 1));
- }
- for(int i = 1; i <= n; ++ i)
- D[i] = 1e7;
- D[st] = 0;
- go(st);
- if(D[en] == 1e7)
- printf("X\n");
- else
- printf("%d\n", D[en]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement