Submission #1217932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217932		thimphu	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	247 ms	35476 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 s, vector<int>& dis) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dis[s] = 0;
    pq.push({0, s});
    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);
    vector<tuple<int, int, int>> edges(m);
    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});
        edges[i] = {a, b, c};
    }
    vector<int> dis1(n, LLONG_MAX);
    vector<int> dis2(n, LLONG_MAX);
    dijkstra(adj, s, dis1);
    dijkstra(adj, t, dis2);
    vector<vector<pair<int, int>>> adj2(n);
    for (auto& [aa, bb, cc] : edges) {
        if (dis1[aa] + dis2[bb] + cc == dis1[t]) {
            adj2[aa].push_back({bb, 0});
            adj2[bb].push_back({aa, 0});
        } else {
            adj2[aa].push_back({bb, cc});
            adj2[bb].push_back({aa, cc});
        }
    }
    vector<int> dis3(n, LLONG_MAX);
    dijkstra(adj2, u, dis3);
    cout << dis3[v];
}

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