Submission #1185273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185273		vincentbucourt1	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	161 ms	24908 KiB

commuter_pass

#define NDEBUG
#include <bits/stdc++.h>
using namespace std;
void fastIO() {ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define s second
#define f first
#define cerr if (false) cerr

const int INF = 1e18;
const int MAXV = 100'020;

int V, E;
int from1, to1, from2, to2;
vector<pair<int,int>> adj[MAXV];
vector<int> distFrom1, distFrom2, distTo2;
bool visited[MAXV];
vector<int> DAG[MAXV];
int dp1[MAXV], dp2[MAXV];
int ans = INF;

void SP (int source, vector<int>& dist) {
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
    }
    dist[source] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,source});
    while (!pq.empty()) {
        pair<int,int> on = pq.top();
        pq.pop();
        if (on.f > dist[on.s]) {
            continue;
        }
        for (pair<int,int> nxt : adj[on.s]) {
            if (dist[nxt.f] > dist[on.s] + nxt.s) {
                dist[nxt.f] = dist[on.s] + nxt.s;
                pq.push({dist[nxt.f],nxt.f});
            }
        }
    }
}

void dfs (int node) {
    // cerr << node << "\n";
    visited[node] = true;
    for (int nxt : DAG[node]) {
        if (!visited[nxt]) {
            dfs(nxt);
        }
        dp1[node] = min(dp1[node], dp1[nxt]);
        dp2[node] = min(dp2[node], dp2[nxt]);
    }
    dp1[node] = min(dp1[node], distFrom2[node]);
    dp2[node] = min(dp2[node], distTo2[node]);
    ans = min(ans, dp1[node] + distTo2[node]);
    ans = min(ans, dp2[node] + distFrom2[node]);
}

signed main() {
    fastIO();
    cin >> V >> E;
    cin >> from1 >> to1 >> from2 >> to2;
    from1--, to1--, from2--, to2--;
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    distFrom1.resize(V+1);
    distFrom2.resize(V+1);
    distTo2.resize(V+1);
    SP(from1, distFrom1);
    SP(from2, distFrom2);
    SP(to2, distTo2);
    // for (int i = 0; i < V; i++) cerr << distFrom1[i] << " ";
    // cerr << "\n";
    memset(visited,false,sizeof(visited));
    queue<int> q;
    q.push(to1);
    visited[to1] = true;
    while (!q.empty()) {
        int on = q.front();
        q.pop();
        for (pair<int,int> prv : adj[on]) {
            if (distFrom1[prv.f] + prv.s == distFrom1[on]) {
                DAG[prv.f].push_back(on);
                if (!visited[prv.f]) {
                    visited[prv.f] = true;
                    q.push(prv.f);
                }
            }
        }
    }
    // for (int i = 0; i < V; i++) {
    //     cerr << i+1 << ":  ";
    //     for (int node : DAG[i]) cerr << node+1 << " ";
    //     cerr << "\n";
    // }
    memset(visited, false, sizeof(visited));
    ans = distFrom2[to2];
    for (int i = 0; i < V; i++) {
        dp1[i] = INF;
        dp2[i] = INF;
    }
    dfs(from1);
    cout << ans << "\n";
}

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