Submission #1235162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235162		orzorzorz	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	265 ms	24656 KiB

commuter_pass

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

#define ll long long
const ll INF = (ll)4e18;
const int MX = 100000;

int n, m;
int S, T, U, V;
vector<pair<int,ll>> adj[MX];
vector<ll> ds, dt, du, dv;
ll dp[MX], dp1[MX], ans;

// Dijkstra：从 src 出发，填充 dist[]
void dijkstra(int src, vector<ll>& dist) {
    dist.assign(n, INF);
    dist[src] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// 正向 DFS：沿 S→T 最短路 DAG，计算 dp[x] = 从 x 开始能到的最小 dv[]
void dfs(int x) {
    if (dp[x] != -1) return;
    if (ds[x] + dt[x] != ds[T]) {
        dp[x] = INF;
        return;
    }
    ll best = dv[x];
    for (auto [y, w] : adj[x]) {
        if (ds[x] + w == ds[y]) {
            dfs(y);
            best = min(best, dp[y]);
        }
    }
    ans = min(ans, du[x] + best);
    dp[x] = best;
}

// 反向 DFS：沿 T→S 最短路 DAG，计算 dp1[x] = 从 x 开始能到的最小 dv[]
void dfs1(int x) {
    if (dp1[x] != -1) return;
    if (ds[x] + dt[x] != ds[T]) {
        dp1[x] = INF;
        return;
    }
    ll best = dv[x];
    for (auto [y, w] : adj[x]) {
        if (dt[x] + w == dt[y]) {
            dfs1(y);
            best = min(best, dp1[y]);
        }
    }
    ans = min(ans, du[x] + best);
    dp1[x] = best;
}

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

    cin >> n >> m;
    cin >> S >> T >> U >> V;
    --S; --T; --U; --V;

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

    dijkstra(S, ds);
    dijkstra(T, dt);
    dijkstra(U, du);
    dijkstra(V, dv);

    // 初始答案：不使用任何重置边时 U->V 最短路
    ans = du[V];

    // 正向遍历
    fill(dp,  dp+n, -1);
    dfs(S);

    // 反向遍历
    fill(dp1, dp1+n, -1);
    dfs1(T);

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

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