Submission #1124244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124244		adaawf	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	228 ms	20132 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, long long int>> g[100005];
long long int n, f[5][100005], d[2][100005];
void dijkstra(int j, int x) {
    for (int i = 1; i <= n; i++) {
        f[j][i] = 1e18;
    }
    f[j][x] = 0;
    priority_queue<pair<long long int, int>> q;
    q.push({0, x});
    while (!q.empty()) {
        long long int x = -q.top().first, u = q.top().second;
        q.pop();
        if (f[j][u] != x) continue;
        for (auto w : g[u]) {
            if (f[j][w.first] > f[j][u] + w.second) {
                f[j][w.first] = f[j][u] + w.second;
                q.push({-f[j][w.first], w.first});
            }
        }
    }
}
long long int dijkstra2(int j, int s, int t) {
    for (int i = 1; i <= n; i++) {
        f[j][i] = 1e18;
        d[0][i] = f[0][i]; d[1][i] = f[1][i];
    }
    f[j][s] = 0;
    priority_queue<pair<long long int, int>> q;
    q.push({0, s});
    while (!q.empty()) {
        long long int x = -q.top().first, u = q.top().second;
        q.pop();
        if (f[j][u] != x) continue;
        for (auto w : g[u]) {
            if (f[j][w.first] > f[j][u] + w.second) {
                f[j][w.first] = f[j][u] + w.second;
                q.push({-f[j][w.first], w.first});
                d[0][w.first] = min(f[0][w.first], d[0][u]);
                d[1][w.first] = min(f[1][w.first], d[1][u]);
            }
            else if (f[j][w.first] == f[j][u] + w.second) {
                if (min(f[0][w.first], d[0][u]) + min(f[1][w.first], d[1][u]) < d[0][w.first] + d[1][w.first]) {
                    d[0][w.first] = min(f[0][w.first], d[0][u]);
                    d[1][w.first] = min(f[1][w.first], d[1][u]);
                }
            }
        }
    }
    return d[0][t] + d[1][t];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        g[u].push_back({v, x});
        g[v].push_back({u, x});
    }
    dijkstra(0, u);
    dijkstra(1, v);
    long long int res = min(f[0][v], dijkstra2(2, s, t));
    cout << res;
}

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