Submission #1241920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241920		khanhtt	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	755 ms	327680 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];

// trace_s holds the DAG of predecessors on *all* shortest s→x paths
vector<int> trace_s[100005];

// temporary trace array used inside Dijkstra (only when recording)
vector<int> trace_tmp[100005];

// store all s→t shortest paths in reverse (t→...→s)
vector<vector<int>> all_paths;
vector<int> current_path;

// Standard Dijkstra: if `record`==true, we fill trace_tmp[]
// otherwise we just compute distances
void dijkstra(int start, int *L, bool record) {
    for (int i = 1; i <= n; i++) {
        L[i] = INF;
        if (record) trace_tmp[i].clear();
    }
    L[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [dist, node] = pq.top(); pq.pop();
        if (dist > L[node]) continue;
        for (auto [nei, w] : adj[node]) {
            if (dist + w < L[nei]) {
                L[nei] = dist + w;
                if (record) {
                    trace_tmp[nei].clear();
                    trace_tmp[nei].push_back(node);
                }
                pq.push({L[nei], nei});
            }
            else if (record && dist + w == L[nei]) {
                // another predecessor on a shortest path
                trace_tmp[nei].push_back(node);
            }
        }
    }
    
    // if this was the run from s, snapshot trace_tmp → trace_s
    if (record) {
        for (int i = 1; i <= n; i++) {
            trace_s[i] = trace_tmp[i];
        }
    }
}

// backtrack *all* reverse‐paths from `x` back to `s` using trace_s[]
void backtrack(int x) {
    current_path.push_back(x);
    if (x == s) {
        all_paths.push_back(current_path);
    } else {
        for (int p : trace_s[x]) {
            backtrack(p);
        }
    }
    current_path.pop_back();
}

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) Run Dijkstra from s *with* recording
    dijkstra(s, Ls, true);

    // 2) Enumerate all shortest s→t paths (in reverse order t→...→s)
    backtrack(t);

    // 3) Run Dijkstra from u and v *without* recording
    dijkstra(u, Lu, false);
    dijkstra(v, Lv, false);

    // 4) For each shortest s→t path, find the best meeting‐point split
    int answer = INF;
    for (auto &path : all_paths) {
        // path is [t, ..., s], so we scan from back to front to go s→t
        int bestLv = INF;
        for (int i = (int)path.size() - 1; i >= 0; --i) {
            bestLv = min(bestLv, Lv[path[i]]);
        }
        for (int i = (int)path.size() - 1; i >= 0; --i) {
            answer = min(answer, Lu[path[i]] + bestLv);
        }
    }

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

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