Submission #944066

#	Time	Username	Problem	Language	Result	Execution time	Memory
944066		tnknguyen_	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	192 ms	23492 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 n, m, S, T, U, V;
long long d[5][sz];
int vi[sz], viid = 0;

//constants
long long INF;
long long ST;

void Dijkstra(int s, int k){
    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});
            }
        }
    } 
}

namespace SUB1{
    bool ok(){
        return (S == U);
    }

    void solve(){
        Dijkstra(V, 3);

        long long ans = 1e18;
        for(int i=1;i<=n;++i){
            if(d[0][i] + d[1][i] == d[0][T]){
                ans = min(ans, d[3][i]);
            }
        }
        cout<<ans;
        //--------------------
        exit(0);
    }
}

long long ds2[305][305]; 
namespace SUB2{ // n <= 300
    bool ok(){
        return (n <= 300);
    }

    void solve(){

        memset(ds2, 0x3f, sizeof(ds2));
        for(int i=1;i<=n;++i){
            ds2[i][i] = 0;
            for(pll p : gr[i]){
                long long v, c;
                tie(v, c) = p;
                ds2[i][v] = c;
            }
        }

        // Floyd - Warshall
        vector<pll> nodes;
        for(int k=1;k<=n;++k){
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    ds2[i][j] = min(ds2[i][j], ds2[i][k] + ds2[k][j]);
                    if(d[0][i] + d[1][j] == ST){
                        nodes.push_back({i, j});
                    }
                }
            }
        }

        Dijkstra(U, 3);
        Dijkstra(V, 4);

        long long ans = ds2[U][V];
        for(pll p : nodes){
            int i, j;
            tie(i, j) = p;
            //U -> i ---> j -> V;
            ans = min(ans, ds2[3][i] + ds2[4][j]);

            //U -> j ---> i -> V;
            ans = min(ans, ds2[4][i] + ds2[3][j]);
        }

        cout<<ans;
        //----------------------
        exit(0);
    }
}

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

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

    cin >> n >> m;
    cin >> S >> T;
    cin >> 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});
    }

    memset(d, 0x3f, sizeof(d));
    INF = d[0][0];

    Dijkstra(S, 0);
    Dijkstra(T, 1);
    ST = d[0][T];

    if(SUB1::ok()){ //S == U
        SUB1::solve();
    }
    if(SUB2::ok()){ //n <= 300
        SUB2::solve();
    }
    

    return 0;
}

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