53252023-04-25 22:07:19CattVázsony vonatjegyet vásárolcpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms26740 KiB
2Elfogadva199ms60120 KiB
subtask220/20
3Elfogadva86ms43092 KiB
4Elfogadva628ms119664 KiB
5Elfogadva469ms99408 KiB
6Elfogadva375ms82360 KiB
7Elfogadva442ms97884 KiB
8Elfogadva363ms81020 KiB
9Elfogadva1.039s145520 KiB
subtask30/15
10Futási hiba324ms77608 KiB
11Elfogadva27ms31964 KiB
12Futási hiba26ms32080 KiB
13Futási hiba67ms40712 KiB
14Futási hiba159ms56016 KiB
subtask40/20
15Futási hiba71ms49924 KiB
16Futási hiba266ms83244 KiB
17Elfogadva57ms45832 KiB
18Elfogadva93ms56192 KiB
19Elfogadva46ms40972 KiB
20Elfogadva104ms51240 KiB
subtask50/45
21Futási hiba12ms29588 KiB
22Elfogadva1.483s203004 KiB
23Elfogadva92ms45016 KiB
24Elfogadva460ms86836 KiB
25Elfogadva354ms84908 KiB
26Elfogadva526ms110580 KiB
27Elfogadva300ms75696 KiB
28Elfogadva1.195s165492 KiB
29Elfogadva197ms61476 KiB
30Elfogadva1.133s157716 KiB
31Futási hiba310ms86328 KiB
32Futási hiba112ms50808 KiB
33Futási hiba449ms108984 KiB
34Elfogadva400ms85948 KiB
35Elfogadva444ms83952 KiB
36Elfogadva389ms82828 KiB
37Elfogadva451ms82304 KiB