Submission #966893

#	Time	Username	Problem	Language	Result	Execution time	Memory
966893		AverageAmogusEnjoyer	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	235 ms	21796 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    int s,t,u,v;
    cin >> s >> t >> u >> v;
    --s,--t,--u,--v;
    vector<vector<pair<int,int>>> adj(n);
    for (int x,y,w;m--;) {
        cin >> x >> y >> w;
        --x,--y;
        adj[x].emplace_back(y,w);
        adj[y].emplace_back(x,w);
    }
    const ll inf = 1e18;
    auto dijkstra = [&](int source) {
        vector<ll> dist(n,inf);
        dist[source] = 0;
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
        q.emplace(0,source);
        while(!q.empty()) {
            auto [d,x] = q.top(); q.pop();
            if (dist[x] != d) { continue; }
            for (auto &[y,w]: adj[x]) if (cmin(dist[y],dist[x]+w)) {
                q.emplace(dist[y],y);
            }
        }
        return dist;
    };
    vector<vector<int>> sp_adj(n);
    auto D = dijkstra(s);
    vector<bool> in_sp(n);
    queue<int> q;
    q.push(t);
    in_sp[t] = true;
    vector<int> in(n);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for (auto &[y,w]: adj[x]) if (D[x] == D[y] + w) {
            sp_adj[x].push_back(y);
            // cout << "added reverse-edge " << 1+x << " " << 1+y << endl;
            in[y]++;
            if (!in_sp[y]) { 
                in_sp[y] = true;
                q.push(y);
            }
        }
    }
    auto DU = dijkstra(u), DV = dijkstra(v); 
    
    vector<ll> dp(n,inf),dp2(n,inf);
    assert(in[t] == 0);
    q.push(t);
    ll ans = DU[v]; 
    while(!q.empty()) {
        int x = q.front(); q.pop();
        cmin(dp[x],DV[x]);
        cmin(dp2[x],DU[x]);
        cmin(ans,dp[x]+DU[x]);
        cmin(ans,dp2[x]+DV[x]);
        for (int &y: sp_adj[x]) {
            cmin(dp[y],dp[x]);
            cmin(dp2[y],dp2[x]);
            if (--in[y] == 0) {
                q.push(y);
            }
        }
    }
    cout << ans << endl;
}

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