Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  1. //Giorgi Kldiashvili
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define ll long long
  6. #define M 1234567LL
  7.  
  8. using namespace std;
  9.  
  10. priority_queue < pair < int, int > > q;
  11. int n, m, st, en;
  12. vector < pair < int, int > > G[200020];
  13. int D[200020];
  14.  
  15. void go(int v)
  16. {
  17. for(int i = 0; i < G[v].size(); ++ i)
  18. {
  19. int to = G[v][i].first;
  20. if(D[to] > D[v] + G[v][i].second)
  21. {
  22. D[to] = D[v] + G[v][i].second;
  23. q.push(make_pair(- D[to], to));
  24. }
  25. }
  26. while(!q.empty())
  27. {
  28. int x = q.top().second;
  29. int y = -q.top().first;
  30. q.pop();
  31. if(D[x] == y)
  32. go(x);
  33. }
  34. }
  35.  
  36. int main()
  37. {
  38. scanf("%d %d %d %d", &n, &m, &st, &en);
  39.  
  40. for(int i = 0; i < m; ++ i)
  41. {
  42. int x, y;
  43. scanf("%d %d", &x, &y);
  44. G[x].push_back(make_pair(y, 0));
  45. G[y].push_back(make_pair(x, 1));
  46. }
  47. for(int i = 1; i <= n; ++ i)
  48. D[i] = 1e7;
  49. D[st] = 0;
  50. go(st);
  51.  
  52. if(D[en] == 1e7)
  53. printf("X\n");
  54. else
  55. printf("%d\n", D[en]);
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement