Submission #1253181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253181		tnknguyen_	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	191 ms	26952 KiB

commuter_pass

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

#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define int long long 

#define pii pair<int, int>
#define fi first
#define se second
#define MASK(k) (1LL << (k))

const int MX = 1e5 + 5;
vector<pii> gr[MX];
vector<int> dag[MX];
int d[5][MX], vi[MX];
int f[2][MX];

void Dijkstra(int S, const int &k){
    memset(d[k], 63, sizeof d[k]); d[k][S] = 0;
    priority_queue<pii> Q; Q.push({0, S});

    while(len(Q)){
        int w, u; tie(w, u) = Q.top(); Q.pop(); w = -w;
        if(w > d[k][u]) continue;

        for(pii p : gr[u]){
            int v, c; tie(v, c) = p;
            if(w + c < d[k][v]){
                d[k][v] = w + c;
                Q.push({-d[k][v], v});
            }
        }
    }
}

deque<int> topo;
void dfs(int p, int u){
    vi[u] = 1;
    for(int v : dag[u]) if(!vi[v]) dfs(u, v);
    topo.push_front(u);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("PATH.inp","r",stdin);
    //freopen("PATH.out","w",stdout);

    int n, m, S, T, U, V; 
    cin >> n >> m;
    cin >> S >> T >> U >> V;

    for(int i=1; i<=m; ++i){
        int u, v, c; cin >> u >> v >> c;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    Dijkstra(S, 0);
    Dijkstra(T, 1);
    Dijkstra(U, 2);
    Dijkstra(V, 3);

    int ST = d[0][T], UV = d[2][V];
    
    // DAG
    for(int u=1; u<=n; ++u){
        for(pii p : gr[u]){
            int v, c; tie(v, c) = p;
            if(d[0][u] + c + d[1][v] == ST) dag[u].push_back(v);
        }
    }

    // DP
    for(int i=1; i<=n; ++i){
        f[0][i] = d[2][i]; // U -> i
        f[1][i] = d[3][i]; // V -> i
    }

    // TOPO
    dfs(0, S);
    for(int u : topo){
        for(int v : dag[u]){
            f[0][v] = min(f[0][v], f[0][u]);
            f[1][v] = min(f[1][v], f[1][u]);
        }
    }

    int ans = UV;
    for(int i=1; i<=n; ++i){
        if(d[0][i] + d[1][i] == ST){
            ans = min({ans, f[0][i] + d[3][i], f[1][i] + d[2][i]});
        }
    }
    cout << ans;

    return 0;
}

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