Submission #567648

#	Time	Username	Problem	Language	Result	Execution time	Memory
567648		aadit_ambadkar	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	368 ms	32260 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<pair<int, ll>>> adj;
vector<vector<int>> nadj;
vector<vector<int>> nradj;
int n, m, s, t, u, v;

int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--;
    adj.resize(n);
    nadj.resize(n);
    nradj.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b; ll c; cin >> a >> b >> c; a--; b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    vector<ll> dist(n);
    vector<bool> vis(n);
    pq.push({0, t});
    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int node = p.second;
        ll len = p.first;
        if (vis[node]) continue;
        dist[node]=len;
        vis[node]=true;
        for (auto i : adj[node]) {
            if (!vis[i.first]) pq.push({len+i.second, i.first});
        }
    }
    fill(vis.begin(), vis.end(), false);
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        if (vis[node]) continue;
        vis[node]=true;
        for (auto i : adj[node]) {
            if (vis[i.first]) continue;
            if (dist[i.first]+i.second==dist[node]) {
                nadj[node].push_back(i.first);
                nradj[i.first].push_back(node);
                q.push(i.first);
            } 
        }
    }
    vector<ll> udist(n), vdist(n);
    while (!pq.empty()) pq.pop();
    fill(vis.begin(), vis.end(), false);
    pq.push({0, u});
    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int node = p.second;
        ll len = p.first;
        if (vis[node]) continue;
        udist[node]=len;
        vis[node]=true;
        for (auto i : adj[node]) {
            if (!vis[i.first]) pq.push({len+i.second, i.first});
        }
    }
    while (!pq.empty()) pq.pop();
    fill(vis.begin(), vis.end(), false);
    pq.push({0, v});
    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int node = p.second;
        ll len = p.first;
        if (vis[node]) continue;
        vdist[node]=len;
        vis[node]=true;
        for (auto i : adj[node]) {
            if (!vis[i.first]) pq.push({len+i.second, i.first});
        }
    }
    vector<int> nchild(n);
    set<int> s;
    vector<ll> dp1(n);
    vector<ll> dp2(n);
    for (int i = 0; i < n; i++) {
        nchild[i] = nadj[i].size();
        if (nchild[i]==0) s.insert(i);
        dp1[i]=vdist[i];
        dp2[i]=udist[i];
    }
    ll ans = 1e18;
    while (!s.empty()) {
        auto node = *s.begin();
        s.erase(s.begin());
        for (auto child : nadj[node]) {
            dp1[node] = min(dp1[node], dp1[child]);
            dp2[node] = min(dp2[node], dp2[child]);
        }
        ans = min(ans, udist[node]+dp1[node]);
        ans = min(ans, vdist[node]+dp2[node]);
        for (auto parent : nradj[node]) {
            if (--nchild[parent]==0) {
                s.insert(parent);
            }
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45