53322023-04-25 22:34:18CattVázsony vonatjegyet vásárolcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms26872 KiB
2Elfogadva217ms59672 KiB
subtask220/20
3Elfogadva93ms43176 KiB
4Elfogadva763ms119808 KiB
5Elfogadva552ms99372 KiB
6Elfogadva391ms82240 KiB
7Elfogadva526ms97688 KiB
8Elfogadva372ms80820 KiB
9Elfogadva1.009s145376 KiB
subtask315/15
10Elfogadva284ms77356 KiB
11Elfogadva29ms31628 KiB
12Elfogadva27ms31948 KiB
13Elfogadva65ms40520 KiB
14Elfogadva123ms55960 KiB
subtask420/20
15Elfogadva79ms48068 KiB
16Elfogadva241ms64020 KiB
17Elfogadva56ms44860 KiB
18Elfogadva90ms55472 KiB
19Elfogadva46ms40760 KiB
20Elfogadva87ms48292 KiB
subtask545/45
21Elfogadva10ms29688 KiB
22Elfogadva1.416s190348 KiB
23Elfogadva90ms43560 KiB
24Elfogadva404ms83740 KiB
25Elfogadva317ms73860 KiB
26Elfogadva509ms98644 KiB
27Elfogadva310ms75684 KiB
28Elfogadva1.006s156396 KiB
29Elfogadva187ms61264 KiB
30Elfogadva1.095s132420 KiB
31Elfogadva273ms66072 KiB
32Elfogadva87ms42708 KiB
33Elfogadva407ms74464 KiB
34Elfogadva312ms68024 KiB
35Elfogadva317ms67972 KiB
36Elfogadva319ms68092 KiB
37Elfogadva319ms67976 KiB