Submission #407571

#	Time	Username	Problem	Language	Result	Execution time	Memory
407571		LittleFlowers__	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	610 ms	19532 KiB

commuter_pass

/*input
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
*/
#include <bits/stdc++.h>
using namespace std;

int n, m, s, t, u, v;
vector<pair<int, int>> ad[100010];

void dij(int fw, vector<long long>&f) {
    fill(f.begin(), f.end(), 1e15);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    q.push({0, fw}); f[fw] = 0;
    while (q.size()) {
        long long w; int u; tie(w, u) = q.top(); q.pop();
        for (auto v : ad[u]) {
            if (f[v.first] > w + v.second) {
                f[v.first] = w + v.second;
                q.push({w + v.second, v.first});
            }
        }
    }
}

main() {
    cin  >> n >> m >> s >> t >> u >> v;

    for (int i = 0; i < m; ++i) {
        int x, y, w; cin >> x >> y >> w;
        ad[x].push_back({y, w});
        ad[y].push_back({x, w});
    }

    vector<long long> fs(n + 1), ft(n + 1), fu(n + 1), fv(n + 1);

    dij(t, ft);
    dij(u, fu);
    dij(v, fv);
    dij(s, fs);


    long long ret = fu[v];
    for (int i = 0; i < 2; ++i) {
        vector<long long> f(n + 1, 1e15), pf(n + 1, 1e15);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; q.push({0, s}); f[s] = 0; pf[s] = fu[s];
        while (q.size()) {
            long long w; int  u; tie(w, u) = q.top(); q.pop();
            ret = min(ret, pf[u] + fv[u]);
            for (auto v : ad[u]) {
                if (fs[v.first] + ft[v.first] == fs[t]) {
                    pf[v.first] = min({pf[v.first], fu[v.first], pf[u]});
                    if (f[v.first] > w + v.second) {
                        f[v.first] = w + v.second;
                        q.push({w + v.second, v.first});
                    }
                }
            }
        }
        swap(fu, fv);
    }
    cout << ret;
}

Compilation message (stderr)

commuter_pass.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      | ^~~~

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