Submission #1000389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000389		Pannda	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	326 ms	32496 KiB

commuter_pass

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

template <class T>
vector<T> dijkstra(const vector<vector<pair<int, T>>> &adj, vector<T> dist) {
    int n = adj.size();
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
    for (int u = 0; u < n; u++) {
        pq.push({dist[u], u});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    constexpr long long INF = 4e18;

    int n, m;
    cin >> n >> m;
    int s, t;
    cin >> s >> t; s--; t--;
    int q, r;
    cin >> q >> r; q--; r--;
    vector<vector<pair<int, long long>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    auto edges_that_may_belong_to_a_shortest_path_from_s_to_t = [&]() -> vector<array<int, 2>> {
        vector<array<int, 2>> ret;
        vector<long long> dist(n, INF); dist[s] = 0;
        dist = dijkstra<long long>(adj, dist);
        vector<vector<int>> rev_dag(n);
        for (int u = 0; u < n; u++) {
            for (auto [v, w] : adj[u]) {
                if (dist[u] + w == dist[v]) {
                    rev_dag[v].push_back(u);
                }
            }
        }
        vector<bool> vis(n, false);
        queue<int> que;
        vis[t] = true;
        que.push(t);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int v : rev_dag[u]) {
                ret.push_back({v, u});
                if (!vis[v]) {
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
        return ret;
    }();

    auto dist_q_downstream = [&]() -> vector<long long> {
        vector<long long> dist(n, INF); dist[q] = 0;
        dist = dijkstra(adj, dist);
        dist = dijkstra([&]() -> vector<vector<pair<int, long long>>> {
                            vector<vector<pair<int, long long>>> adj(n);
                            for (auto [u, v] : edges_that_may_belong_to_a_shortest_path_from_s_to_t) adj[u].push_back({v, 0});
                            return adj;
                        }(), dist);
        dist = dijkstra(adj, dist);
        return dist;
    }();

    auto dist_q_upstream = [&]() -> vector<long long> {
        vector<long long> dist(n, INF); dist[q] = 0;
        dist = dijkstra(adj, dist);
        dist = dijkstra([&]() -> vector<vector<pair<int, long long>>> {
                            vector<vector<pair<int, long long>>> adj(n);
                            for (auto [u, v] : edges_that_may_belong_to_a_shortest_path_from_s_to_t) adj[v].push_back({u, 0});
                            return adj;
                        }(), dist);
        dist = dijkstra(adj, dist);
        return dist;
    }();

    cout << min(dist_q_downstream[r], dist_q_upstream[r]) << '\n';

}

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