53252023-04-25 22:07:19CattVázsony vonatjegyet vásárolcpp17Runtime error 20/1001.483s203004 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(to[x].size() < to[y].size()) swap(x, y);

    p[y] = x;
    for(ll sz : to[y]) {
        to[x].insert(sz);
    }
    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[root(sz)]) continue;
        dfs(root(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(ll i = 1; i <= n; i++) {
        p[i] = i;
        for(auto sz : g[i]) {
            if(dist[sz.first] < dist[i]) {
                to[i].insert(sz.first);
            }
            else if(dist[sz.first] > dist[i]) {
                to[sz.first].insert(i);
            }
        }
    }
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] == dist[i]) {
                connect(sz.first, 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);
    volt.assign(n+1, 0);
    
    tav[root(a)] = 0;
    queue<ll> sor;
    sor.push(root(a));
    while(!sor.empty()) {
        ll cur = sor.front();
        sor.pop();

        volt[cur] = 1;

        for(ll sz : to[cur]) {
            sz = root(sz);
            if(volt[sz]) continue;
            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 != a) {
        cur = parent[cur];
        mo.insert(root(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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted12ms26740 KiB
2Accepted199ms60120 KiB
subtask220/20
3Accepted86ms43092 KiB
4Accepted628ms119664 KiB
5Accepted469ms99408 KiB
6Accepted375ms82360 KiB
7Accepted442ms97884 KiB
8Accepted363ms81020 KiB
9Accepted1.039s145520 KiB
subtask30/15
10Runtime error324ms77608 KiB
11Accepted27ms31964 KiB
12Runtime error26ms32080 KiB
13Runtime error67ms40712 KiB
14Runtime error159ms56016 KiB
subtask40/20
15Runtime error71ms49924 KiB
16Runtime error266ms83244 KiB
17Accepted57ms45832 KiB
18Accepted93ms56192 KiB
19Accepted46ms40972 KiB
20Accepted104ms51240 KiB
subtask50/45
21Runtime error12ms29588 KiB
22Accepted1.483s203004 KiB
23Accepted92ms45016 KiB
24Accepted460ms86836 KiB
25Accepted354ms84908 KiB
26Accepted526ms110580 KiB
27Accepted300ms75696 KiB
28Accepted1.195s165492 KiB
29Accepted197ms61476 KiB
30Accepted1.133s157716 KiB
31Runtime error310ms86328 KiB
32Runtime error112ms50808 KiB
33Runtime error449ms108984 KiB
34Accepted400ms85948 KiB
35Accepted444ms83952 KiB
36Accepted389ms82828 KiB
37Accepted451ms82304 KiB