Submission #887547

#	Time	Username	Problem	Language	Result	Execution time	Memory
887547		Perl32	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	331 ms	38600 KiB

commuter_pass

// I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const ll INFL = (ll) 1e18 + 1e9;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t, su, sv;
    cin >> n >> m >> s >> t >> su >> sv;
    --s, --t, --su, --sv;
    vector<vector<pair<int, ll>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    function<vector<ll>(int)> dijkstra = [&](int from) {
        set<pair<ll, int>> st;
        vector<ll> dist(n, INFL);
        dist[from] = 0ll;
        st.insert({0ll, from});
        while (!st.empty()) {
            int u = st.begin()->second;
            st.erase(st.begin());
            for (auto [to, w] : g[u]) {
                if (dist[to] > dist[u] + w) {
                    st.erase({dist[to], to});
                    dist[to] = dist[u] + w;
                    st.insert({dist[to], to});
                }
            }
        }
        return dist;
    };
    vector<ll> distS = dijkstra(s);
    vector<bool> used(n, false), can(n, false);
    can[t] = true;
    vector<vector<int>> dag(n);
    function<void(int)> Dfs1 = [&](int u) {
        used[u] = true;
        for (auto [to, w] : g[u]) {
            if (distS[to] != distS[u] + w) continue;
            if (!used[to]) Dfs1(to);
            can[u] = can[u] || can[to];
            if (can[to]) {
                dag[u].emplace_back(to);
            }
        }
    };
    Dfs1(s);
    fill(used.begin(), used.end(), false);
    vector<ll> distV = dijkstra(sv), distU = dijkstra(su), closeV(n, INFL), closeU(n, INFL);;
    function<void(int)> Dfs2 = [&](int u) {
        used[u] = true;
        closeV[u] = distV[u];
        closeU[u] = distU[u];
        for (auto to : dag[u]) {
            if (!used[to]) Dfs2(to);
            closeV[u] = min(closeV[u], closeV[to]);
            closeU[u] = min(closeU[u], closeU[to]);
        }
    };
    Dfs2(s);
    ll ans = distU[sv];
    for (int i = 0; i < n; ++i) {
        ans = min({ans, closeV[i] + distU[i], closeU[i] + distV[i]});
    }
    cout << ans;
}

/*

 */

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:38:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |             for (auto [to, w] : g[u]) {
      |                       ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:54:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         for (auto [to, w] : g[u]) {
      |                   ^

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