Submission #868966

#	Time	Username	Problem	Language	Result	Execution time	Memory
868966		rockstar	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	383 ms	29776 KiB

commuter_pass

//#pragma GCC optimize("O3,unroll-loops,inline,fast-math")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()
#define int ll

constexpr int INF = numeric_limits<int>::max() / 2;

vector<int> dijkstra(vector<vector<pair<int, int>>> &gr, int s) {
    int n = gr.size();
    vector<int> dist(n, INF);
    dist[s] = 0;
    set<pair<int, int>> st;
    st.insert({0, s});
    while (!st.empty()) {
        int v = st.begin()->second;
        st.erase(st.begin());
        for (auto [u, cost] : gr[v])
            if (dist[u] > dist[v] + cost) {
                st.erase({dist[u], u});
                dist[u] = dist[v] + cost;
                st.insert({dist[u], u});
            }
    }
    return dist;
}

void solve() {
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    --s, --t, --u, --v;
    vector<vector<pair<int, int>>> gr(n);
    for (int i = 0, a, b, c; i < m; ++i) {
        cin >> a >> b >> c;
        --a, --b;
        gr[a].push_back({b, c});
        gr[b].push_back({a, c});
    }
    auto ds = dijkstra(gr, s), dt = dijkstra(gr, t);
    vector<vector<int>> dag(n);
    for (int i = 0; i < n; ++i)
        for (auto [j, cost] : gr[i])
            if (ds[i] + dt[j] + cost == ds[t])
                dag[i].push_back(j);
    auto solve = [&](vector<int> &du, vector<int> dv) -> int {
        int res = INF;
        vector<bool> used(n, false);
        auto dfs = [&](auto dfs, int a) -> int {
            if (!used[a]) {
                used[a] = true;
                for (int b : dag[a])
                    dv[a] = min(dv[a], dfs(dfs, b));
                res = min(res, dv[a] + du[a]);
            }
            return dv[a];
        };
        for (int i = 0; i < n; ++i)
            dfs(dfs, i);
        return res;
    };
    auto du = dijkstra(gr, u), dv = dijkstra(gr, v);
    cout << min(solve(du, dv), solve(dv, du));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
}

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