Quipex

temp

Apr 2nd, 2017
408
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <string>
  8. #include <iterator>
  9. #include <iomanip>
  10. #include <queue>
  11. #include <stack>
  12. using namespace std;
  13.  
  14. #define sqr(x) ((x)*(x))
  15. #define cbr(x) ((x)*(x)*(x))
  16. #define rep(c, i, n) for((i)=(c); (i)<(n); (i)++)
  17. /**
  18. //Geometry
  19.  
  20. struct pt { long long x, y; };
  21. double vecmul(pt a, pt b) { return (a.x*b.y - b.x*a.y); }
  22.  
  23. double dist(double ax, double ay, double bx, double by) { return sqrt(sqr(ax - bx) + sqr(ay - by)); }
  24. */
  25.  
  26. //DBG
  27. template<typename T, typename T2>void printarr(T  a[], T2 sz, T2 beg = 0) { for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  28. #define DBG(a)         cout<<#a<<"="<<(a)<<"\n"
  29. #define DBG2(a,b)       cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  30. #define DBG3(a,b,c)     cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  31.  
  32. //Files
  33. #define FILE_MODE(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
  34.  
  35. //Constants
  36. #define PI    3.1415926535897932
  37. #define INF   1011111111
  38. #define LLINF 1000111000111000111LL
  39. #define eps   1e-14
  40. #define mod   1000000007
  41. #define ll long long
  42. #define ull unsigned long long
  43. //-------------------------------------------------
  44. #define N 50010
  45. //7 9 1 7 3 6 1 3 6 7 1 4 5 6  1 2 2 5 3 5  4 7
  46. int n, m, s, f;
  47. vector<int> vertex[N];
  48. queue<int> bfsQ;
  49. vector<int> path[N];
  50. int vis[N];
  51. int dist[N];
  52.  
  53. int main() {
  54.     cin >> n >> m >> s >> f;
  55.     s--; f--;
  56.     int i,x,y,j;
  57.     rep(0,i,m) {
  58.         cin >> x >> y;
  59.         x--; y--;
  60.         vertex[x].push_back(y);
  61.         vertex[y].push_back(x);
  62.     }
  63.     //visited 0, distance to everything is inf.
  64.     memset(dist, -1, sizeof dist);
  65.     memset(vis, 0, sizeof vis);
  66.  
  67.     dist[s] = 0;
  68.     vis[s] = 1;
  69.     path[s].push_back(s);
  70.  
  71.     bfsQ.push(s);
  72.     int minDist=-1;
  73.     while (!bfsQ.empty()) {
  74.         int u = bfsQ.front();
  75.  
  76.         bfsQ.pop();
  77.  
  78.         for (int i : vertex[u]) {
  79.             if (!vis[i]) {
  80.                 vis[i] = 1;
  81.                 dist[i] = dist[u]+1;
  82.                 path[i] = path[u];
  83.                 path[i].push_back(i);
  84.                 bfsQ.push(i);
  85.             }
  86.         }
  87.     }
  88.     cout << dist[f] << endl;
  89.     rep(0, i, path[f].size()) {
  90.         path[f][i]++;
  91.     }
  92.     copy(path[f].begin(), path[f].end(), ostream_iterator<int>(cout, " "));
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment