Submission #769386

#	Time	Username	Problem	Language	Result	Execution time	Memory
769386		Alora	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	264 ms	15252 KiB

commuter_pass

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

const long long INF = 1e18;
vector<vector<pair<int, int>>> g;

void djikstra(int src, vector<long long> &sp) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    sp[src] = 0;
    pq.push({0, src});
    while (pq.size()) {
        int u = pq.top().second;
        pq.pop();
        for (auto [v, w] : g[u])
            if (sp[v] > sp[u] + w)
                sp[v] = sp[u] + w, pq.push({sp[v], v});
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    --S, --T, --U, --V;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    vector<vector<long long>> sp(4, vector<long long> (n, INF));
    djikstra(S, sp[0]);
    djikstra(T, sp[1]);
    djikstra(U, sp[2]);
    djikstra(V, sp[3]);
    long long d1 = INF, d2 = INF;
    for (int i = 0; i < n; i++) {
        if (sp[0][i] + sp[1][i] == sp[0][T]) {
            d1 = min(d1, sp[2][i]);
            d2 = min(d2, sp[3][i]);
        }
    }
    long long TH1 = min (sp[0][U] + sp[1][V], sp[0][V] + sp[1][U]);
    long long TH2 = d1 + d2;
    cout << min({TH1, TH2, sp[2][V]});
}

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