Submission #1086188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086188		f0rizen	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	202 ms	25588 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, w;
};

vector<vector<Edge>> dag;
vector<ll> da, db;
vector<ll> dp_a, dp_b;
vector<bool> used;
ll ans = infll;

void dfs(int v) {
    used[v] = 1;
    dp_a[v] = da[v];
    dp_b[v] = db[v];
    for (auto [u, w] : dag[v]) {
        if (!used[u]) {
            dfs(u);
        }
        dp_a[v] = min(dp_a[v], dp_a[u]);
        dp_b[v] = min(dp_b[v], dp_b[u]);
    }
    ans = min(ans, dp_a[v] + db[v]);
    ans = min(ans, dp_b[v] + da[v]);
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m;
    cin >> n >> m;
    int s, t, a, b;
    cin >> s >> t >> a >> b;
    --s, --t, --a, --b;
    vector<vector<Edge>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    auto dijkstra = [&](int s) {
        vector<ll> dp(n, infll);
        dp[s] = 0;
        using pii = pair<ll, int>;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({dp[s], s});
        while (!pq.empty()) {
            auto [_, v] = pq.top();
            pq.pop();
            if (_ > dp[v]) {
                continue;
            }
            for (auto [u, w] : g[v]) {
                if (dp[u] > dp[v] + w) {
                    dp[u] = dp[v] + w;
                    pq.push({dp[u], u});
                }
            }
        }
        return dp;
    };
    vector<ll> ds = dijkstra(s);
    vector<ll> dt = dijkstra(t);
    dag.resize(n);
    for (int i = 0; i < n; ++i) {
        for (auto [j, w] : g[i]) {
            if (ds[i] + w + dt[j] == ds[t]) {
                dag[i].push_back({j, w});
            }
        }
    }
    da = dijkstra(a);
    db = dijkstra(b);
    dp_a.resize(n);
    dp_b.resize(n);
    used.resize(n);
    ans = da[b];
    dfs(s);
    cout << ans << "\n";
    return 0;
}

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