53262023-04-25 22:07:35CattVázsony vonatjegyet vásárolcpp17Időlimit túllépés 55/1001.605s165484 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 != root(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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms26904 KiB
2Elfogadva215ms60236 KiB
subtask220/20
3Elfogadva93ms42960 KiB
4Elfogadva740ms119508 KiB
5Elfogadva537ms98996 KiB
6Elfogadva344ms81860 KiB
7Elfogadva507ms97328 KiB
8Elfogadva319ms80560 KiB
9Elfogadva824ms145144 KiB
subtask315/15
10Elfogadva307ms77184 KiB
11Elfogadva29ms31552 KiB
12Elfogadva26ms31660 KiB
13Elfogadva67ms40252 KiB
14Elfogadva162ms55560 KiB
subtask420/20
15Elfogadva100ms50604 KiB
16Elfogadva405ms84392 KiB
17Elfogadva59ms45424 KiB
18Elfogadva107ms55920 KiB
19Elfogadva48ms40732 KiB
20Elfogadva104ms50968 KiB
subtask50/45
21Elfogadva14ms29180 KiB
22Időlimit túllépés1.605s102956 KiB
23Elfogadva90ms44880 KiB
24Elfogadva400ms86660 KiB
25Elfogadva372ms84836 KiB
26Elfogadva523ms110588 KiB
27Elfogadva268ms75696 KiB
28Elfogadva994ms165484 KiB
29Elfogadva199ms61328 KiB
30Elfogadva1.136s157264 KiB
31Elfogadva333ms86248 KiB
32Elfogadva122ms50624 KiB
33Elfogadva532ms110236 KiB
34Elfogadva407ms85824 KiB
35Elfogadva446ms83876 KiB
36Elfogadva442ms82844 KiB
37Elfogadva460ms82192 KiB