5332 2023. 04. 25 22:34:18 Catt Vázsony vonatjegyet vásárol cpp17 Elfogadva 100/100 1.416s 190348 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxN = 2e5 + 5;


vector<vector<pair<ll, ll> > > g;
vector<ll> dist;
vector<ll> p(maxN), s(maxN, 1);
vector<set<ll> > to(maxN);
vector<bool> volt(maxN, 0);

ll root(ll x) {
    if(p[x] == x) return x;

    return p[x] = root(p[x]);
}

void connect(ll x, ll y) {
    x = root(x);
    y = root(y);

    if(x == y) return;
    if(s[x] < s[y]) swap(x, y);

    p[y] = x;
    s[x] += s[y];
}

void dijkstra(ll start) {
    priority_queue<pair<ll, ll> > pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();

        ll w = -curr.first, x = curr.second;
        if(dist[x] != -1) continue;
        dist[x] = w;
        for(pair<ll, ll> sz : g[x]) {
            if(dist[sz.first] != -1) continue;
            pq.push({-w-sz.second, sz.first});
        }
    }
}

void dfs(int x) {
    volt[x] = 1;
    for(int sz : to[x]) {
        if(volt[sz]) continue;
        dfs(sz);
    }
}

int main() {

    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    
    ll n,m,a,b;
    cin >> n >> m >> a >> b;
    g.resize(n+1);
    dist.resize(n+1, -1);

    for(ll i = 0; i < m; i++) {
        ll x,y,z;
        cin >> x >> y >> z;

        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }

    dijkstra(b);
    for(int i = 1; i <= n; i++) p[i] = i;
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] == dist[i]) {
                connect(sz.first, i);
            }
        }
    }
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] < dist[i]) {
                to[root(i)].insert(root(sz.first));
            }
            else if(dist[sz.first] > dist[i]) {
                to[root(sz.first)].insert(root(i));
            }
        }
    }

    dfs(root(a));
    vector<ll> be(n+1, 0);
    for(ll i = 1; i <= n; i++) {

        if(!volt[i] || root(i) != i) continue;
        for(ll sz : to[i]) be[root(sz)]++;
    }

    vector<ll> tav(n+1, -1), parent(n+1, -1);
    
    tav[root(a)] = 0;
    queue<ll> sor;
    sor.push(root(a));
    while(!sor.empty()) {
        ll cur = sor.front();
        sor.pop();

        for(ll sz : to[cur]) {
            be[sz]--;
            if(tav[sz] < tav[cur] + s[cur]) {
                tav[sz] = tav[cur] + s[cur];
                parent[sz] = cur;
            }
            if(be[sz] == 0) {
                sor.push(sz);
            }
        }
    }

    set<ll> mo = {root(b)};
    ll cur = root(b);
    while(cur != root(a)) {
        cur = parent[cur];
        mo.insert(cur);
    }
    
    vector<ll> ki;
    for(ll i = 1; i <= n; i++) {
        if(mo.find(root(i)) != mo.end()) ki.push_back(i);
    }

    cout << ki.size() << "\n";
    for(ll sz : ki) cout << sz << ' ';
    
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 12ms 26872 KiB
2 Elfogadva 217ms 59672 KiB
subtask2 20/20
3 Elfogadva 93ms 43176 KiB
4 Elfogadva 763ms 119808 KiB
5 Elfogadva 552ms 99372 KiB
6 Elfogadva 391ms 82240 KiB
7 Elfogadva 526ms 97688 KiB
8 Elfogadva 372ms 80820 KiB
9 Elfogadva 1.009s 145376 KiB
subtask3 15/15
10 Elfogadva 284ms 77356 KiB
11 Elfogadva 29ms 31628 KiB
12 Elfogadva 27ms 31948 KiB
13 Elfogadva 65ms 40520 KiB
14 Elfogadva 123ms 55960 KiB
subtask4 20/20
15 Elfogadva 79ms 48068 KiB
16 Elfogadva 241ms 64020 KiB
17 Elfogadva 56ms 44860 KiB
18 Elfogadva 90ms 55472 KiB
19 Elfogadva 46ms 40760 KiB
20 Elfogadva 87ms 48292 KiB
subtask5 45/45
21 Elfogadva 10ms 29688 KiB
22 Elfogadva 1.416s 190348 KiB
23 Elfogadva 90ms 43560 KiB
24 Elfogadva 404ms 83740 KiB
25 Elfogadva 317ms 73860 KiB
26 Elfogadva 509ms 98644 KiB
27 Elfogadva 310ms 75684 KiB
28 Elfogadva 1.006s 156396 KiB
29 Elfogadva 187ms 61264 KiB
30 Elfogadva 1.095s 132420 KiB
31 Elfogadva 273ms 66072 KiB
32 Elfogadva 87ms 42708 KiB
33 Elfogadva 407ms 74464 KiB
34 Elfogadva 312ms 68024 KiB
35 Elfogadva 317ms 67972 KiB
36 Elfogadva 319ms 68092 KiB
37 Elfogadva 319ms 67976 KiB