Submission #884066

#	Time	Username	Problem	Language	Result	Execution time	Memory
884066		Sharky	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	288 ms	39472 KiB

commuter_pass

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

#define int long long
const int INF = 1e18;

struct edge {
    int u, v, w;
};

int n, ans;
vector<vector<pair<int, int>>> adj(100005);
vector<vector<int>> g(100005), g2(100005);
vector<int> du(100005), dv(100005);
vector<int> deg1(100005, 0), deg2(100005, 0);
vector<edge> edges;

void dijk(int s, vector<int>& di, vector<vector<pair<int, int>>>& G) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    for (int i = 1; i <= n; i++) di[i] = INF;
    di[s] = 0;
    q.push({di[s], s});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (di[u] != d) continue;
        for (auto& [v, w] : G[u]) {
            if (di[u] + w < di[v]) {
                di[v] = di[u] + w;
                q.push({di[v], v});
            }
        }
    }
}

void dijk2(vector<int>& dp, vector<vector<int>>& G, vector<int>& deg) {
    queue<int> q;
    vector<int> di(n + 1);
    for (int i = 1; i <= n; i++) {
        di[i] = du[i];
        if (!deg[i]) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // cout << u << '\n';
        ans = min(ans, di[u] + dv[u]);
        for (auto& v : G[u]) {
            deg[v]--;
            di[v] = min(di[v], di[u]);
            if (deg[v] == 0) q.push(v);
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    while (m--) {
        int x, y, w;
        cin >> x >> y >> w;
        edges.push_back({x, y, w});
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    vector<int> ds(n+1), dt(n+1), dp(n+1), dp2(n+1);
    dijk(s, ds, adj); dijk(t, dt, adj); dijk(u, du, adj); dijk(v, dv, adj);
    vector<bool> nodes(n+1, 0);
    for (int i = 1; i <= n; i++) if (ds[i] + dt[i] == ds[t]) nodes[i] = 1;
    for (auto& [x, y, w] : edges) {
        if (ds[x] + dt[y] + w == ds[t]) {
            g[x].push_back(y);
            g2[y].push_back(x);
            deg1[y]++, deg2[x]++;
            // cout << x << ' ' << y << '\n';
        } else if (ds[y] + dt[x] + w == ds[t]) {
            g[y].push_back(x);
            g2[x].push_back(y);
            deg1[x]++, deg2[y]++;
            // cout << x << " " << y << '\n';
        }
    }
    ans = du[v];
    dijk2(dp, g, deg1); dijk2(dp2, g2, deg2);
    cout << ans << '\n';
}

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