Submission #833479

#	Time	Username	Problem	Language	Result	Execution time	Memory
833479		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2047 ms	34912 KiB

commuter_pass

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

#define ll long long
#define pll pair<long long, long long>
#define pllm pair<vector<long long>, long long>

const ll inf = 1e18;
const int maxn = 100005;
// const int maxn = 50;
int n, m, s, t, u, v;

pllm dist[maxn]; // <parent, dist>
ll ndist[maxn]; // <parent, dist>
priority_queue<pll, vector<pll>, greater<pll>> pq;
map<int, int> adj[maxn];

void nullifyparents(ll idx) {
    if (idx == s) return;
    for (auto i : dist[idx].first) {
        adj[idx][i] = 0;
        adj[i][idx] = 0;

        nullifyparents(i);
    }
}

int main() {
    for (int i = 0; i < maxn; i++) {
        dist[i] = {{-1}, inf};
        ndist[i] = inf;
    }

    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = c;
        adj[b][a] = c;
    }

    pq.push({0, s});
    dist[s] = {{s}, 0};

    while (!pq.empty()) {
        auto [currdist, idx] = pq.top();

        for (auto &[b, c] : adj[idx]) {
            if (currdist + c < dist[b].second) { // potential?
                dist[b] = {{idx}, currdist + c};
                pq.push({currdist+c, b});
            } 
            if (currdist + c == dist[b].second) {
                dist[b].first.push_back(idx);
            }
        }

        pq.pop(); 
    }

    nullifyparents(t);

    pq.push({0, u});
    ndist[u] = 0;

    while (!pq.empty()) {
        auto [currdist, idx] = pq.top();

        for (auto [b, c] : adj[idx]) {
            if (currdist + c < ndist[b]) {
                ndist[b] = currdist+c;
                pq.push({currdist+c, b});
            } 
        }

        pq.pop(); 
    }

    cout << ndist[v] << endl;

    return 0;
}

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