Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <cmath>
- #include <cstring>
- #include <string>
- #include <iterator>
- #include <iomanip>
- #include <queue>
- #include <stack>
- using namespace std;
- #define sqr(x) ((x)*(x))
- #define cbr(x) ((x)*(x)*(x))
- #define rep(c, i, n) for((i)=(c); (i)<(n); (i)++)
- /**
- //Geometry
- struct pt { long long x, y; };
- double vecmul(pt a, pt b) { return (a.x*b.y - b.x*a.y); }
- double dist(double ax, double ay, double bx, double by) { return sqrt(sqr(ax - bx) + sqr(ay - by)); }
- */
- //DBG
- 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; }
- #define DBG(a) cout<<#a<<"="<<(a)<<"\n"
- #define DBG2(a,b) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
- #define DBG3(a,b,c) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
- //Files
- #define FILE_MODE(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
- //Constants
- #define PI 3.1415926535897932
- #define INF 1011111111
- #define LLINF 1000111000111000111LL
- #define eps 1e-14
- #define mod 1000000007
- #define ll long long
- #define ull unsigned long long
- //-------------------------------------------------
- #define N 50010
- //7 9 1 7 3 6 1 3 6 7 1 4 5 6 1 2 2 5 3 5 4 7
- int n, m, s, f;
- vector<int> vertex[N];
- queue<int> bfsQ;
- vector<int> path[N];
- int vis[N];
- int dist[N];
- int main() {
- cin >> n >> m >> s >> f;
- s--; f--;
- int i,x,y,j;
- rep(0,i,m) {
- cin >> x >> y;
- x--; y--;
- vertex[x].push_back(y);
- vertex[y].push_back(x);
- }
- //visited 0, distance to everything is inf.
- memset(dist, -1, sizeof dist);
- memset(vis, 0, sizeof vis);
- dist[s] = 0;
- vis[s] = 1;
- path[s].push_back(s);
- bfsQ.push(s);
- int minDist=-1;
- while (!bfsQ.empty()) {
- int u = bfsQ.front();
- bfsQ.pop();
- for (int i : vertex[u]) {
- if (!vis[i]) {
- vis[i] = 1;
- dist[i] = dist[u]+1;
- path[i] = path[u];
- path[i].push_back(i);
- bfsQ.push(i);
- }
- }
- }
- cout << dist[f] << endl;
- rep(0, i, path[f].size()) {
- path[f][i]++;
- }
- copy(path[f].begin(), path[f].end(), ostream_iterator<int>(cout, " "));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment