Submission #1166318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166318		merciless_lassie	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	250 ms	32560 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int N = 1e5 + 5;
#define II pair<int, int>
#define fi first
#define se second

int n, m;
int s, t, U, V;
vector<II> adj[N], adj2[N];
vector<int> parent[N];
int f[N], f2[N];

template<class X, class Y> bool mini(X &x, const Y y) {
    if (x > y) return x = y, 1;
    return 0;
}

void dijkstra(int start, int dist[], vector<II> g[], bool track_parents = false) {
    fill(dist, dist + n + 1, LLONG_MAX);
    priority_queue<II, vector<II>, greater<II>> pq;
    pq.push({0, start});
    dist[start] = 0;
    
    while (!pq.empty()) {
        II u = pq.top(); pq.pop();
        if (u.fi != dist[u.se]) continue;
        
        for (II v : g[u.se]) {
            int new_dist = dist[u.se] + v.fi;
            if (mini(dist[v.se], new_dist)) {
                pq.push({dist[v.se], v.se});
                if (track_parents) {
                    parent[v.se].clear();
                    parent[v.se].push_back(u.se);
                }
            } else if (dist[v.se] == new_dist && track_parents) {
                parent[v.se].push_back(u.se);
            }
        }
    }
}

void build_adj2() {
    queue<int> q;
    vector<bool> visited(n + 1, false);
    q.push(t);
    visited[t] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : parent[u]) {
            adj2[u].push_back({0, v});
            adj2[v].push_back({0, u});
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (II j : adj[i]) {
            if (f[i] + j.fi == f[j.se]) continue; // Already added as shortest path
            adj2[i].push_back(j);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m; 
    cin >> s >> t >> U >> V;

    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({c, v});
        adj[v].push_back({c, u});
    }

    dijkstra(s, f, adj, true);
    build_adj2();
    dijkstra(U, f2, adj2);

    cout << (f2[V] == LLONG_MAX ? -1 : f2[V]) << "\n";
}

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