Submission #1241931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241931		khanhtt	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2096 ms	17084 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

static const int INF = 1e9;

int n, m, s, t, u, v;
int Ls[100005], Lu[100005], Lv[100005];
vector<pair<int,int>> adj[100005];
vector<int> trace[100005];

int answer = INF;

// Standard Dijkstra: when calc==true we also build the predecessor‐lists in trace[]
void dijkstra(int start, int *L, bool calc) {
    for(int i = 1; i <= n; i++) {
        L[i] = INF;
        if(calc) trace[i].clear();
    }
    L[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start});
    
    while(!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        if(d > L[x]) continue;
        for(auto [y, w] : adj[x]) {
            if(d + w < L[y]) {
                L[y] = d + w;
                if(calc) {
                    trace[y].clear();
                    trace[y].push_back(x);
                }
                pq.push({L[y], y});
            }
            else if(calc && d + w == L[y]) {
                // another shortest‐path predecessor
                trace[y].push_back(x);
            }
        }
    }
}

// DFS from t back to s, carrying along the best (min) Lu[] and Lv[] seen so far
void back(int x, int best_u, int best_v) {
    best_u = min(best_u, Lu[x]);
    best_v = min(best_v, Lv[x]);
    
    if(x == s) {
        // we've reached s, record candidate answer
        answer = min(answer, best_u + best_v);
        return;
    }
    for(int p : trace[x]) {
        back(p, best_u, best_v);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    // 1) Distances from u and v (no tracing needed)
    dijkstra(u, Lu, false);
    dijkstra(v, Lv, false);

    // 2) Distances *and* trace‐lists from s
    dijkstra(s, Ls, true);

    // 3) Explore every shortest s→t path by DFS from t back to s
    back(t, INF, INF);

    cout << answer << "\n";
    return 0;
}

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