Submission #1236572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236572		imann	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2083 ms	327680 KiB

commuter_pass

#include <iostream>
#include <array>
#include <vector>
#include <queue>
#include <limits>

const int MAX_N = 1000*100 + 2;

std::array<std::vector<std::pair<int, int>>, MAX_N> graph;

void dijkstra(int startNode, std::array<int, MAX_N> &dist) {
    using T = std::pair<int, int>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
    dist.fill(std::numeric_limits<int>::max());
    pq.push({0, startNode});
    dist[startNode] = 0;
    while (!pq.empty()) {
        auto [sDist, node] = pq.top();
        pq.pop();
        if (sDist != dist[node])
            continue;
        for (auto nei : graph[node]) {
            if (dist[nei.first] > sDist + nei.second) {
                dist[nei.first] = sDist + nei.second;
                pq.push({dist[nei.first], nei.first});
            }
        }
    }
}

int solve(int n, int m, int s, int t, int u, int v) {
    std::array<int, MAX_N> sDist, tDist, uDist, vDist;
    dijkstra(s, sDist);
    dijkstra(t, tDist);
    dijkstra(u, uDist);
    dijkstra(v, vDist);
    int uvDist = uDist[v];
    int stDist = sDist[t];

    using T = std::pair<int, int>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
    std::array<int, MAX_N> sFromUDist, sFromVDist, ssDist;
    sFromUDist.fill(std::numeric_limits<int>::max());
    sFromVDist.fill(std::numeric_limits<int>::max());
    ssDist.fill(std::numeric_limits<int>::max());
    ssDist[s] = 0;
    pq.push({0, s});
    sFromUDist[s] = uDist[s];
    sFromVDist[s] = vDist[s];
    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();
        if (dist != ssDist[node])
            continue;
        for (auto nei : graph[node]) {
            if (ssDist[nei.first] > dist + nei.second) {
                ssDist[nei.first] = dist + nei.second;
                pq.push({ssDist[nei.first], nei.first});
                sFromUDist[nei.first] = std::min(sFromUDist[node], uDist[nei.first]);
                sFromVDist[nei.first] = std::min(sFromVDist[node], vDist[nei.first]);
            } else if (ssDist[nei.first] == dist + nei.second) {
                sFromUDist[nei.first] = std::min(sFromUDist[nei.first], sFromUDist[node]);
                sFromUDist[nei.first] = std::min(sFromUDist[nei.first], uDist[nei.first]);
                sFromVDist[nei.first] = std::min(sFromVDist[nei.first], sFromVDist[node]);
                sFromVDist[nei.first] = std::min(sFromVDist[nei.first], vDist[nei.first]);
                pq.push({ssDist[nei.first], nei.first});
            }
        }
    }

    pq = {};
    std::array<int, MAX_N> tFromUDist, tFromVDist, ttDist;
    tFromVDist.fill(std::numeric_limits<int>::max());
    tFromUDist.fill(std::numeric_limits<int>::max());
    ttDist.fill(std::numeric_limits<int>::max());
    ttDist[t] = 0;
    pq.push({0, t});
    tFromVDist[t] = vDist[t];
    tFromUDist[t] = uDist[t];
    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();
        if (dist != ttDist[node])
            continue;
        for (auto nei : graph[node]) {
            if (ttDist[nei.first] > dist + nei.second) {
                ttDist[nei.first] = dist + nei.second;
                pq.push({ttDist[nei.first], nei.first});
                tFromVDist[nei.first] = std::min(tFromVDist[node], vDist[nei.first]);
                tFromUDist[nei.first] = std::min(tFromUDist[node], uDist[nei.first]);
            } else if (ttDist[nei.first] == dist + nei.second) {
                tFromVDist[nei.first] = std::min(tFromVDist[nei.first], tFromVDist[node]);
                tFromVDist[nei.first] = std::min(tFromVDist[nei.first], vDist[nei.first]);
                tFromUDist[nei.first] = std::min(tFromUDist[nei.first], tFromUDist[node]);
                tFromUDist[nei.first] = std::min(tFromUDist[nei.first], uDist[nei.first]);
                pq.push({ttDist[nei.first], nei.first});
            }
        }
    }
    int ans = std::numeric_limits<int>::max();
    for (int i = 0; i < n; ++i) {
        if (sDist[i] + tDist[i] == stDist) {
            ans = std::min(ans, sFromUDist[i] + tFromVDist[i]);
            ans = std::min(ans, sFromVDist[i] + tFromUDist[i]);
        }
    }
    if (ans > uvDist)
        return uvDist;
    return ans;
}

int main() {
    int n, m; std::cin >> n >> m;
    int s, t; std::cin >> s >> t; s--; t--;
    int u, v; std::cin >> u >> v; u--; v--;
    for (int i = 0; i < m; ++i) {
        int a, b, c; std::cin >> a >> b >> c; a--; b--;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    std::cout << solve(n, m, s, t, u, v) << std::endl;
}

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