316582026-09-11 21:03:59Kristof0306Adott ponton átmenő legrövidebb kör **cpp17Elfogadva 100/10029ms2496 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pair<int, int>>;
using vai = vector<array<int, 3>>;

#define x 
#define y second
#define all(x) x.begin(), x.end()

vector<vi> connect;

void solve() {
    int n, m, p; cin >> n >> m >> p; p--;
    connect.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        connect[u].push_back(v);
        connect[v].push_back(u);
    }

    vector<vi> ans(n);
    ans[p].push_back(p);
    queue<int> q;
    q.push(p);
    vi parent(n, -1);

    vi best(n+1, INT_MAX);

    while (!q.empty()) {
        int node = q.front(); q.pop();

        for (int i : connect[node]) {
            if (ans[i].empty()) {
                ans[i] = ans[node];
                ans[i].push_back(i);
                parent[i] = node;
                q.push(i);
            } else {
                if (i != parent[node] && ans[i][1] != ans[node][1]) {
                    //cout << ans[i].size()+ans[node].size()-1 << "\n";
                    if (ans[i].size()+ans[node].size()-1 < best.size()) {
                        reverse(all(ans[node])); 
                        int hely = ans[node][ans[node].size()-1];
                        ans[node].pop_back();

                        best = ans[i];
                        for (int j : ans[node]) best.push_back(j);

                        ans[node].push_back(hely);
                        reverse(all(ans[node]));
                    }
                }
            }

        }
    } if (best.size() == n+1) {
        cout << -1;
    } else {
        cout << best.size() << "\n";
        for (int i : best) cout << i+1 << " ";
    }
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    int t=1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva6/61ms316 KiB
2Elfogadva6/61ms508 KiB
3Elfogadva6/61ms316 KiB
4Elfogadva6/61ms316 KiB
5Elfogadva6/61ms316 KiB
6Elfogadva6/61ms424 KiB
7Elfogadva6/61ms508 KiB
8Elfogadva6/628ms2236 KiB
9Elfogadva6/67ms836 KiB
10Elfogadva6/69ms820 KiB
11Elfogadva6/612ms1232 KiB
12Elfogadva6/617ms1848 KiB
13Elfogadva7/729ms2496 KiB
14Elfogadva7/77ms1844 KiB
15Elfogadva7/728ms2356 KiB
16Elfogadva7/729ms2496 KiB