Submission #702209

#	Time	Username	Problem	Language	Result	Execution time	Memory
702209		bebra	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	299 ms	28448 KiB

commuter_pass

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

#define dbg(x) cerr << #x << ": " << x << endl;


const ll INF = 1e18;
const int MAX_N = 1e5 + 5;
vector<pair<int, int>> g[MAX_N];
vector<int> new_g[MAX_N];
ll dp[2][MAX_N];
ll dist[4][MAX_N];


void dfs_order(int v, vector<int>& order, vector<bool>& used) {
    used[v] = true;
    for (auto u : new_g[v]) {
        if (!used[u]) {
            dfs_order(u, order, used);
        }
    }
    order.push_back(v);
}


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

    int n, m;
    cin >> n >> m;

    int s1, t1;
    cin >> s1 >> t1;
    --s1, --t1;

    int s2, t2;
    cin >> s2 >> t2;
    --s2, --t2;

    vector<tuple<int, int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int w;
        cin >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
        edges[i] = {u, v, w};
    }

    {
        array<int, 4> start_vertices = {s2, t2, s1, t1};
        for (int i = 0; i < 4; ++i) {
            int s = start_vertices[i];
            
            fill_n(dist[i], n, INF);
            vector<bool> used(n);

            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
            pq.emplace(0, s);
            while (!pq.empty()) {
                auto [curr_dist, v] = pq.top();
                pq.pop();
                if (used[v]) continue;
                used[v] = true;
                dist[i][v] = curr_dist;
                for (const auto& [u, w] : g[v]) {
                    if (used[u] || curr_dist + w >= dist[i][u]) continue;
                    dist[i][u] = curr_dist + w;
                    pq.emplace(dist[i][u], u);
                }
            }
        }
    }

    {
        for (auto [u, v, w] : edges) {
            for (int t = 0; t <= 1; ++t) {
                if (dist[2][u] + w == dist[2][v] && dist[2][v] + dist[3][v] == dist[2][t1]) {
                    new_g[u].push_back(v);
                }
                swap(u, v);
            }
        }
    }

    vector<int> order;
    {
        vector<bool> used(n);
        dfs_order(s1, order, used);
        reverse(order.begin(), order.end());
    }

    fill_n(dp[0], n, INF);
    fill_n(dp[1], n, INF);

    ll ans = dist[0][t2];
    for (auto v : order) {
        for (int t = 0; t <= 1; ++t) {
            dp[t][v] = min(dp[t][v], dist[t][v]);
            for (auto u : new_g[v]) {
                dp[t][u] = min(dp[t][u], dp[t][v]);
            }
            ans = min(ans, dp[t][v] + dist[t ^ 1][v]);
        }
    }

    cout << ans << '\n';

    return 0;
}

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