53322023-04-25 22:34:18CattVázsony vonatjegyet vásárolcpp17Accepted 100/1001.416s190348 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted12ms26872 KiB
2Accepted217ms59672 KiB
subtask220/20
3Accepted93ms43176 KiB
4Accepted763ms119808 KiB
5Accepted552ms99372 KiB
6Accepted391ms82240 KiB
7Accepted526ms97688 KiB
8Accepted372ms80820 KiB
9Accepted1.009s145376 KiB
subtask315/15
10Accepted284ms77356 KiB
11Accepted29ms31628 KiB
12Accepted27ms31948 KiB
13Accepted65ms40520 KiB
14Accepted123ms55960 KiB
subtask420/20
15Accepted79ms48068 KiB
16Accepted241ms64020 KiB
17Accepted56ms44860 KiB
18Accepted90ms55472 KiB
19Accepted46ms40760 KiB
20Accepted87ms48292 KiB
subtask545/45
21Accepted10ms29688 KiB
22Accepted1.416s190348 KiB
23Accepted90ms43560 KiB
24Accepted404ms83740 KiB
25Accepted317ms73860 KiB
26Accepted509ms98644 KiB
27Accepted310ms75684 KiB
28Accepted1.006s156396 KiB
29Accepted187ms61264 KiB
30Accepted1.095s132420 KiB
31Accepted273ms66072 KiB
32Accepted87ms42708 KiB
33Accepted407ms74464 KiB
34Accepted312ms68024 KiB
35Accepted317ms67972 KiB
36Accepted319ms68092 KiB
37Accepted319ms67976 KiB