Submission #621497

#	Time	Username	Problem	Language	Result	Execution time	Memory
621497		elkernos	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	392 ms	24960 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef pair<int, int> pii;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, s1, e1, s2, e2;
    cin >> n >> m >> s1 >> e1 >> s2 >> e2;
    vector g(n + 1, vector<pii>());
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    const int oo = 1e18;
    auto dijkstra = [&](int st) {
        priority_queue<pii, vector<pii>, greater<pii>> q;
        vector<int> d(n + 1, oo);
        q.emplace(d[st] = 0, st);
        while(!q.empty()) {
            auto [ter, u] = q.top();
            q.pop();
            if(ter != d[u]) {
                continue;
            }
            for(auto [to, len] : g[u]) {
                if(d[to] > d[u] + len) {
                    q.emplace(d[to] = d[u] + len, to);
                }
            }
        }
        return d;
    };
    vector<int> dd1 = dijkstra(s2);
    vector<int> dd2 = dijkstra(e2);
    int ans = dd1[e2];
    vector<int> dp1(n + 1, oo), dp2(n + 1, oo), d1(n + 1, oo), d2(n + 1, oo);
    for(int rep : {0, 1}) {
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.emplace(d1[s1] = 0, s1);
        dp1[s1] = dd1[s1];
        while(!q.empty()) {
            auto [ter, u] = q.top();
            q.pop();
            if(ter != d1[u]) {
                continue;
            }
            for(auto [to, len] : g[u]) {
                if(d1[to] > d1[u] + len) {
                    dp1[to] = min(dp1[u], dd1[to]);
                    q.emplace(d1[to] = d1[u] + len, to);
                }
                else if(d1[to] == d1[u] + len) {
                    dp1[to] = min({dp1[to], dp1[u], dd1[to]});
                }
            }
        }
        swap(s1, e1);
        swap(d1, d2);
        swap(dp1, dp2);
    }
    for(int i = 1; i <= n; i++) {
        if(d1[i] + d2[i] == d1[e1]) {
            ans = min(ans, min(dp1[i], dp2[i]) + dd2[i]);
        }
    }
    cout << ans << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:43:13: warning: unused variable 'rep' [-Wunused-variable]
   43 |     for(int rep : {0, 1}) {
      |             ^~~

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