Submission #1218326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218326		thimphu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	158 ms	23820 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, m, s, t, u, v;

void dijkstra(vector<vector<pair<int, int>>>& adj, int ss, vector<int>& dis) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dis[ss] = 0;
    pq.push({0, ss});
    while (!pq.empty()) {
        auto [curw, curn] = pq.top();
        pq.pop();
        if (curw != dis[curn]) continue;
        for (auto& [nextn, nextw] : adj[curn]) {
            if (curw + nextw < dis[nextn]) {
                dis[nextn] = curw + nextw;
                pq.push({dis[nextn], nextn});
            }
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> s >> t >> u >> v;
    s--;
    t--;
    u--;
    v--;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    vector<int> dis1(n, LLONG_MAX);
    vector<int> dis2(n, LLONG_MAX);
    dijkstra(adj, u, dis1);
    dijkstra(adj, v, dis2);
    priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> pq;
    vector<pair<int, int>> dis(n, {LLONG_MAX, LLONG_MAX});
    dis[s] = {0, dis1[s] + dis2[s]};
    pq.push({0, dis1[s] + dis2[s], dis1[s], dis2[s], s});
    while (!pq.empty()) {
        auto [curw, curs, curu, curv, curn] = pq.top();
        pq.pop();
        if (make_pair(curw, curs) != dis[curn]) continue;
        for (auto& [nextn, nextw] : adj[curn]) {
            int nu = min(curu, dis1[nextn]), nv = min(curv, dis2[nextn]);
            if (curw + nextw < dis[nextn].first) {
                dis[nextn] = {curw + nextw, nu + nv};
                pq.push({dis[nextn].first, nu + nv, nu, nv, nextn});
            } else if (curw + nextw == dis[nextn].first and nu + nv < dis[nextn].second) {
                dis[nextn].second = nu + nv;
                pq.push({dis[nextn].first, nu + nv, nu, nv, nextn});
            }
        }
    }
    cout << min(dis[t].second, dis1[v]);
}

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