Submission #944254

#	Time	Username	Problem	Language	Result	Execution time	Memory
944254		tnknguyen_	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	280 ms	34012 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define pll pair<long long, long long>

const int sz = 1e5 + 5;
vector<pll> gr[sz];
long long d[5][sz];
long long f[5][sz];
int n, m, S, T, U, V;

//constants
long long ST;
long long UV;

void Dijkstra(int k, int s){
    priority_queue<pll> q;
    d[k][s] = 0;
    q.push({0, s});

    while(q.size()){
        long long w, u;
        tie(w, u) = q.top();
        w = -w;
        q.pop();

        if(w > d[k][u]){
            continue;
        }
        for(pll p : gr[u]){
            long long v, c;
            tie(v, c) = p;
            if(w + c < d[k][v]){
                d[k][v] = w + c;
                q.push({-d[k][v], v});
            }
        }
    }
}

vector<int> dag[sz];
int vi[sz];
void build_DAG(int v){
    vi[v] = 1;
    for(pll p : gr[v]){
        long long u, c;
        tie(u, c) = p;
        if(d[0][u] + c + d[1][v] == ST){
            dag[u].push_back(v);
            if(vi[u] == 0){
                build_DAG(u);
            }
        }
    }
}

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

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

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

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

    while(m--){
        int u, v, c;
        cin>>u>>v>>c;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    memset(d, 63, sizeof(d));
    Dijkstra(0, S);
    Dijkstra(1, T);
    Dijkstra(2, U);
    Dijkstra(3, V);

    ST = d[0][T];
    UV = d[2][V];

    build_DAG(T);
    topo(S);

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

    for(int u : tp){
        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]);
        }
    }

    long long 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