Submission #696489

#	Time	Username	Problem	Language	Result	Execution time	Memory
696489		therealpain	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	355 ms	28900 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) a = b; else return false; return true;
}

const int N = 1e5 + 7;

bool isIn[N];
int n, m, s, t, u, v;
long long distS[N], distT[N], distU[N], distV[N], dpU[N], dpV[N];
vector <int> p[N][2];
vector <pair <int, int>> adj[N];

void dijkstra(int s, long long dist[]) {
    for (int i = 1; i < N; ++i) dist[i] = 1e18;
    priority_queue <pair <long long, int>> heap;
    dist[s] = 0;
    heap.emplace(0, s);
    while (heap.size()) {
        auto [da, a] = heap.top();
        heap.pop();
        da = -da;
        if (da != dist[a]) continue;
        for (auto [b, c] : adj[a]) {
            if (mini(dist[b], da + c)) heap.emplace(-dist[b], b);

        }
    }
}

void dfs1(int a) {
    dpU[a] = distV[a];
    for (int b : p[a][0]) {
        if (dpU[b] < 0) dfs1(b);
        mini(dpU[a], dpU[b]);
    }
}

void dfs2(int b) {
    dpV[b] = distV[b];
    for (int a : p[b][1]) {
        if (dpV[a] < 0) dfs2(a);
        mini(dpV[b], dpV[a]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    dijkstra(s, distS);
    dijkstra(t, distT);
    dijkstra(u, distU);
    dijkstra(v, distV);

    for (int a = 1; a <= n; ++a) {
        for (auto [b, c] : adj[a])
            if (distS[a] + distT[b] + c == distS[t]) {
                isIn[a] = isIn[b] = true;
                p[a][0].emplace_back(b);
                p[b][1].emplace_back(a);
            }
    }

    memset(dpU, -1, sizeof dpU);
    memset(dpV, -1, sizeof dpV);
    dfs1(s);
    dfs2(t);

    long long ans = distU[v];
    for (int i = 1; i <= n; ++i) {
        if (isIn[i]) mini(ans, distU[i] + min(dpU[i], dpV[i]));
    }

    cout << ans;

}

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