Submission #1032589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032589		VectorLi	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	430 ms	20848 KiB

commuter_pass

#include <bits/stdc++.h>
#define long long long
#define y0 asdad13
#define y1 dsgfsf4we

using namespace std;

const int N = (int) 1E5;
const long B = numeric_limits<long>::max();

int n, m;
int x0, y0;
int x1, y1;
long d[4][N];
long c;
vector<pair<int, int>> e[N];

void Dijkstra0(int x, int i) {
    set<pair<long, int>> q;

    fill(d[i], d[i] + n, B);
    d[i][x] = 0;
    q.insert({0, x});

    while (not q.empty()) {
        int u = q.begin() -> second;
        q.erase(q.begin());
        for (auto [v, w] : e[u]) {
            if (d[i][v] > d[i][u] + w) {
                q.erase({d[i][v], v});
                d[i][v] = d[i][u] + w;
                q.insert({d[i][v], v});
            }
        }
    }
}

long f[N];
long d0[N];

void Dijkstra1(int x) {
    set<pair<long, int>> q;

    fill(d0, d0 + n, B);
    d0[x] = 0;
    f[x] = d[0][x];
    q.insert({0, x});
    c = min(c, f[x] + d[1][x]);

    assert(x0 != y1 || x1 != y0);
    while (not q.empty()) {
        int u = q.begin() -> second;
        q.erase(q.begin());
        for (auto [v, w] : e[u]) {
            if (d0[v] > d0[u] + w) {
                q.erase({d0[v], v});
                d0[v] = d0[u] + w;
                f[v] = min(f[u], d[0][v]);
                if (d[2][u] + w + d[3][v] == d[2][y0]) {
                    c = min(c, f[v] + d[1][v]);
                }
                q.insert({d0[v], v});
            } else if (d0[v] == d0[u] + w) {
                f[v] = min(f[v], f[u]);
                // if (d[2][v] + d[3][v] == d[2][y0]) {
                //     c = min(c, f[v] + d[1][v]);
                // }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        // if (i == x) {
        //     continue;
        // }
        if (d[2][i] + d[3][i] == d[2][y0]) {
            c = min(c, d[1][i] + f[i]);
        }
    }

    // cout << d[0][5 - 1] << "\n";
    // for (int i = 0; i < n; i++) {
    //     cout << i + 1 << " " << f[i] << "\n";
    // }
}

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

    cin >> n >> m;
    cin >> x0 >> y0;
    x0 = x0 - 1, y0 = y0 - 1;
    cin >> x1 >> y1;
    x1 = x1 - 1, y1 = y1 - 1;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u = u - 1, v = v - 1;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    Dijkstra0(x1, 0);
    Dijkstra0(y1, 1);
    Dijkstra0(x0, 2);
    Dijkstra0(y0, 3);
    c = d[0][y1];
    Dijkstra1(x0);
    Dijkstra1(y0);
    cout << c << "\n";

    return 0;
}

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