5331 2023. 04. 25 22:31:31 Catt Vázsony vonatjegyet vásárol cpp17 Időlimit túllépés 55/100 1.605s 156216 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;
    for(ll sz : to[y]) {
        to[x].insert(root(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(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(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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 12ms 26868 KiB
2 Elfogadva 216ms 59688 KiB
subtask2 20/20
3 Elfogadva 93ms 43176 KiB
4 Elfogadva 670ms 119796 KiB
5 Elfogadva 521ms 99620 KiB
6 Elfogadva 363ms 82448 KiB
7 Elfogadva 479ms 97640 KiB
8 Elfogadva 370ms 80684 KiB
9 Elfogadva 841ms 145264 KiB
subtask3 15/15
10 Elfogadva 270ms 77088 KiB
11 Elfogadva 27ms 31404 KiB
12 Elfogadva 27ms 31476 KiB
13 Elfogadva 67ms 40080 KiB
14 Elfogadva 123ms 55424 KiB
subtask4 20/20
15 Elfogadva 82ms 48752 KiB
16 Elfogadva 272ms 63192 KiB
17 Elfogadva 57ms 45028 KiB
18 Elfogadva 96ms 55392 KiB
19 Elfogadva 52ms 40124 KiB
20 Elfogadva 96ms 47856 KiB
subtask5 0/45
21 Elfogadva 14ms 29132 KiB
22 Időlimit túllépés 1.605s 96404 KiB
23 Elfogadva 86ms 43308 KiB
24 Elfogadva 400ms 83504 KiB
25 Elfogadva 340ms 73716 KiB
26 Elfogadva 588ms 98480 KiB
27 Elfogadva 307ms 75420 KiB
28 Elfogadva 1.195s 156216 KiB
29 Elfogadva 187ms 61264 KiB
30 Elfogadva 1.115s 132352 KiB
31 Elfogadva 301ms 66056 KiB
32 Elfogadva 87ms 42704 KiB
33 Elfogadva 412ms 74464 KiB
34 Elfogadva 317ms 67772 KiB
35 Elfogadva 321ms 67768 KiB
36 Elfogadva 324ms 68140 KiB
37 Elfogadva 326ms 67976 KiB