53312023-04-25 22:31:31CattVázsony vonatjegyet vásárolcpp17Időlimit túllépés 55/1001.605s156216 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms26868 KiB
2Elfogadva216ms59688 KiB
subtask220/20
3Elfogadva93ms43176 KiB
4Elfogadva670ms119796 KiB
5Elfogadva521ms99620 KiB
6Elfogadva363ms82448 KiB
7Elfogadva479ms97640 KiB
8Elfogadva370ms80684 KiB
9Elfogadva841ms145264 KiB
subtask315/15
10Elfogadva270ms77088 KiB
11Elfogadva27ms31404 KiB
12Elfogadva27ms31476 KiB
13Elfogadva67ms40080 KiB
14Elfogadva123ms55424 KiB
subtask420/20
15Elfogadva82ms48752 KiB
16Elfogadva272ms63192 KiB
17Elfogadva57ms45028 KiB
18Elfogadva96ms55392 KiB
19Elfogadva52ms40124 KiB
20Elfogadva96ms47856 KiB
subtask50/45
21Elfogadva14ms29132 KiB
22Időlimit túllépés1.605s96404 KiB
23Elfogadva86ms43308 KiB
24Elfogadva400ms83504 KiB
25Elfogadva340ms73716 KiB
26Elfogadva588ms98480 KiB
27Elfogadva307ms75420 KiB
28Elfogadva1.195s156216 KiB
29Elfogadva187ms61264 KiB
30Elfogadva1.115s132352 KiB
31Elfogadva301ms66056 KiB
32Elfogadva87ms42704 KiB
33Elfogadva412ms74464 KiB
34Elfogadva317ms67772 KiB
35Elfogadva321ms67768 KiB
36Elfogadva324ms68140 KiB
37Elfogadva326ms67976 KiB