Submission #1218976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218976		niwrad	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	186 ms	30120 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

long long inf = 1e17;
int n;

vector<vector<pair<int, long long>>> graph;

vector<long long> dijkstra(int s) {
    vector<long long> dis(n, inf);
    vector<int> vis(n);
    dis[s] = 0;
    priority_queue<pair<long long, int>> pq;
    pq.push({0, s});
    while (pq.size() > 0) {
        auto t = pq.top();
        pq.pop();
        if (vis[t.second]) {
            continue;
        }
        vis[t.second] = 1;
        for (auto adj : graph[t.second]) {
            if (adj.second + dis[t.second] < dis[adj.first]) {
                dis[adj.first] = adj.second + dis[t.second];
                pq.push({-dis[adj.first], adj.first});
            }
        }
    }
    return dis;
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--;
    graph.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b; long long c;
        cin >> a >> b >> c;
        graph[--a].push_back({--b, c});
        graph[b].push_back({a, c});
    }
    vector<long long> u_dis = dijkstra(u);
    vector<long long> u_par = u_dis;
    vector<long long> u_child = u_dis;
    vector<long long> v_dis = dijkstra(v);
    vector<long long> dis(n, inf);
    vector<vector<int>> par(n);
    vector<int> vis(n);
    dis[s] = 0;
    priority_queue<pair<long long, int>> pq;
    pq.push({0, s});
    while (pq.size() > 0) {
        auto t = pq.top();
        pq.pop();
        if (vis[t.second]) {
            continue;
        }
        vis[t.second] = 1;
        for (auto adj : graph[t.second]) {
            if (adj.second + dis[t.second] < dis[adj.first]) {
                dis[adj.first] = adj.second + dis[t.second];
                par[adj.first].clear();
                par[adj.first].push_back(t.second);
                pq.push({-dis[adj.first], adj.first});
            } else if (adj.second + dis[t.second] == dis[adj.first]) {
                par[adj.first].push_back(t.second);
            }
        }
    }
    vector<int> on(n);
    queue<int> q;
    on[t] = 1;
    q.push(t);
    while (q.size() > 0) {
        int f = q.front();
        q.pop();
        for (auto adj : par[f]) {
            if (!on[adj]) {
                on[adj] = 1;
                q.push(adj);
            }
        }
    }
    vector<vector<int>> child(n);
    for (int i = 0; i < n; i++) {
        if (on[i]) {
            for (int j = 0; j < par[i].size(); j++) {
                child[par[i][j]].push_back(i);
            }
            pq.push({-u_dis[i], i});
        }
    }
    while (pq.size() > 0) {
        auto t = pq.top();
        pq.pop();
        long long d = -t.first;
        if (u_par[t.second] >= d) {
            queue<int> q;
            q.push(t.second);
            while (q.size() > 0) {
                for (auto adj : par[q.front()]) {
                    if (u_par[adj] > d && on[adj]) {
                        u_par[adj] = d;
                        q.push(adj);
                    }
                }
                q.pop();
            }
        }
        if (u_child[t.second] >= d) {
            queue<int> q;
            q.push(t.second);
            while (q.size() > 0) {
                for (auto adj : child[q.front()]) {
                    if (u_child[adj] > d && on[adj]) {
                        u_child[adj] = d;
                        q.push(adj);
                    }
                }
                q.pop();
            }
        }
    }
    long long out = inf;
    for (int i = 0; i < n; i++) {
        long long m_u = min(u_child[i], u_par[i]);
        out = min(out, m_u + v_dis[i]);
    }
    cout << out << "\n";
}

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