Submission #482089

#	Time	Username	Problem	Language	Result	Execution time	Memory
482089		bill_lin	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	291 ms	26896 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
 
const ll INF = 1e15;

int n;
vector<vector<pii>> adj;
vector<vector<int>> spadj;

vector<ll> dp;
vector<ll> sp, dist_u, dist_v;

ll dfs(int node) {
    if (dp[node] != -1) return dp[node];
    ll best = dist_v[node];
    
    for (int dest : spadj[node]) {
        best = min(best, dfs(dest));
    }
    return dp[node] = best;
}

vector<ll> dijkstra(int start_node) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pll, vector<pll>, greater<pll>> q;
    dist[start_node] = 0;
    q.push({0, start_node});
    
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        ll curr_cost = p.first, node = p.second;
        for (pii &edge : adj[node]) {
            int dest = edge.first, edge_cost = edge.second;
            if (dist[dest] > curr_cost + edge_cost) {
                dist[dest] = curr_cost + edge_cost;
                q.push({dist[dest], dest});
            }
        }
    }
    
    return dist;
}



int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    
    adj.resize(n + 1);
    spadj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        adj[u].push_back({v, cost});
        adj[v].push_back({u, cost});
    }

    // shortest path, dist to u, dist to v
    sp = dijkstra(S), dist_u = dijkstra(U), dist_v = dijkstra(V);
    vector<bool> vis(n + 1, false);
    // construct the shortest path
    queue<int> q;
    q.push(T);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        ll mn_dist = INF;
        for (pii &edge : adj[node]) {
            mn_dist = min(mn_dist, sp[edge.first]);
        }
        for (pii &edge : adj[node]) {
            int dest = edge.first, edge_cost = edge.second;
            if (sp[dest] + edge_cost == sp[node]) {
                spadj[node].push_back(dest);
                if (!vis[dest]) {
                    vis[dest] = true;
                    q.push(dest);
                }
            }
        }
    }
    
    // dfs from T, calculate, reverse spadj and dfs from S and recalculate
    ll best = dist_v[U];
    dp = vector<ll>(n + 1, -1);
    
    for (int i = 1; i <= n; i++) {
        dfs(i);
        best = min(best, dp[i] + dist_u[i]);
    }
    
    
    vector<vector<int>> tmp(n + 1);
    // reverse the edges
    for (int i = 1; i <= n; i++) {
        for (int j : spadj[i]) {
            tmp[j].push_back(i);
        }
    }
    
    spadj = tmp;
    dp = vector<ll>(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        dfs(i);
        best = min(best, dp[i] + dist_u[i]);
    }
    
    cout << best << '\n';
    
    
    
}

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