eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кратчайший путь

опубликовано 21.01.2024, 08:04:35

include <bits/stdc++.h>

define intt long long

define pb push_back

define pii pair<int,int>

define pll pair<intt,intt>

define F first

define S second

using namespace std; const int inf = 1e9+5; bool used[100005]; intt d[100005]; intt par[100005]; vector<intt>g[100005]; void bfs(intt node,intt n){ for(int i=1;i<=n;i++){ used[i] = false; d[i] = inf; } queue<int>q; q.push(node); d[node] = 0; while(!q.empty()){ int cur = q.front(); q.pop(); if(used[cur]) continue; used[cur] = true; for(int i:g[cur]){ if(d[cur] + 1 < d[i]){ d[i] = d[cur] + 1; q.push(i); par[i] = cur; } } } } int main(){ intt n,m,a,b,x,y; cin >> n >> m >> a >> b; while(m--){ cin >> x >> y; g[x].pb(y); g[y].pb(x); } bfs(a,n); if(!used[b]){ cout << -1; return 0; } int curp = b; vector<int>res; while(curp!=a){ res.pb(curp); curp = par[curp]; } res.pb(a); reverse(res.begin(),res.end()); cout << d[b] << endl; for(int i:res){ cout << i << " "; } }