Submission #366993

#	Time	Username	Problem	Language	Result	Execution time	Memory
366993		zecookiez	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	438 ms	29100 KiB

commuter_pass

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

const long long INF = 1e17;

const int MAXN = 100005;

vector<pair<int, long long>> adj[2][MAXN];
long long dp[MAXN][4];

int main() {

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V;
    --S; --T; --U; --V;
    for(int i = 0; i < M; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        adj[0][a].emplace_back(b, c);
        adj[0][b].emplace_back(a, c);
    }

    auto dij = [&](const int src, const int id){
        vector<long long> dist(N, INF);
        vector<bool> vis(N, false);
        priority_queue<pair<long long, int>> pq;
        dist[src] = 0;
        pq.push(make_pair(0, src));
        while(!pq.empty()){
            long long d = -pq.top().first;
            int node = pq.top().second;
            pq.pop();
            if(dist[node] < d) continue;
            if(vis[node]) continue;
            dist[node] = d;
            vis[node] = true;
            for(auto nxt : adj[id][node]){
                if(dist[nxt.first] > d + nxt.second){
                    dist[nxt.first] = d + nxt.second;
                    pq.push(make_pair(-dist[nxt.first], nxt.first));
                }
            }
        }
        return dist;
    };

    vector<long long> dS = dij(S, 0);
    vector<long long> dU = dij(U, 0);
    vector<long long> dV = dij(V, 0);
    vector<long long> dT = dij(T, 0);

    vector<pair<long long, int>> closest;
    for(int i = 0; i < N; ++i){
        closest.emplace_back(dS[i], i);
        dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = INF;
    }
    sort(closest.begin(), closest.end());
    // 0 -- no U, no V
    // 1 -- yes U, no V
    // 2 -- no U, yes V
    // 3 -- yes
    dp[S][0] = 0;
    dp[S][1] = dU[S];
    dp[S][2] = dV[S];
    dp[S][3] = dU[S] + dV[S];
    for(auto i : closest){
        int node = i.second;
        for(auto j : adj[0][node]){
            int nxt = j.first;
            // if lies on the shortest path tree
            if(dS[node] != dS[nxt] + j.second) continue;
            for(int k = 0; k < 4; ++k){
                for(int l = 0; l < 4; ++l){
                    long long ree = 0;
                    if(k & 1) ree += dU[node];
                    if(k & 2) ree += dV[node];
                    dp[node][k | l] = min(dp[node][k | l], dp[nxt][l] + ree);
                }
            }
        }
    }
    cout << min(dV[U], dp[T][3]) << endl;

    return 0;
}

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