Submission #944149

#	Time	Username	Problem	Language	Result	Execution time	Memory
944149		tnknguyen_	Commuter Pass (JOI18_commuter_pass)	C++14	40 / 100	270 ms	29444 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 dp[5][sz];
long long d[5][sz];

//constants
long long INF;
long long ST;


// ------------- FUNCTIONS ------------- //
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});
            }
        }
    } 
}

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);
    //         }
    //     }
    // }

    vector<long long> d_dag(n + 5, INF);
    priority_queue<pll> q;
    q.push({0, S});
    d_dag[S] = 0;
    
    while(q.size()){
        long long w, u;
        tie(w, u) = q.top();
        w = -w;
        q.pop();

        if(w > d_dag[u]){
            continue;
        }

        for(pll p : gr[u]){
            long long v, c;
            tie(v, c) = p;
            if(w + c < d_dag[v]){
                d_dag[v] = w + c;
                q.push({-d_dag[v], v});
                dag[u].clear();
                dag[v].push_back(u);
            }
            else if(w + c == d_dag[v]){
                dag[v].push_back(u);
            }
        }
    } 
}   

void topo(int u){
    vi[u] = 2;
    for(int v : dag[u]){
        dp[1][u] = min(dp[1][u], dp[1][v]);
        dp[2][u] = min(dp[2][u], dp[2][v]);

        if(vi[v] != 2){
            topo(v);
        }
    }

    priority_queue<pll> q;
}

// ------------- SUBTASK ------------- //
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, 63, sizeof(ds2));
        for(int i=1;i<=n;++i){
            ds2[i][i] = 0;
            for(pll p : gr[i]){
                ds2[i][p.first] = p.second;
            }
        }

        // Floyd - Warshall
        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]);
                }
            }
        }

        long long ans = ds2[U][V];
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(ds2[S][i] + ds2[i][j] + ds2[j][T] == ST){
                    ans = min(ans, ds2[U][i] + ds2[j][V]);
                    ans = min(ans, ds2[U][j] + ds2[i][V]);
                }
            }
        }

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

namespace SUB3{
    void solve(){
        build_DAG(T);

        Dijkstra(U, 3);
        Dijkstra(V, 4); 
        
        memset(dp, 63, sizeof(dp));
        for(int i=1;i<=n;++i){
            dp[1][i] = d[3][i];
            dp[2][i] = d[4][i]; 
        }

        // topo(S);
        long long ans = d[3][V];

        priority_queue<pll> q;
        vector<long long> ds3(n+5, INF);    
        ds3[T] = d[3][T];

        ds3 = vector<long long>(n + 5, INF);
        ds3[T] = d[4][T];
        while(q.size()){
            long long w, u;
            tie(w, u) = q.top();
            w = -w;
            q.pop();

            if(w > ds3[u]){
                continue;
            }
            ans = min(ans, w + d[4][u]);

            for(int v : dag[u]){
                long long c = min(w, d[4][u]);
                if(c < ds3[v]){
                    ds3[v] = c;
                    q.push({-c, v});
                }
            }
        }

        ds3 = vector<long long>(n + 5, INF);
        ds3[T] = d[4][T];
        while(q.size()){
            long long w, u;
            tie(w, u) = q.top();
            w = -w;
            q.pop();

            if(w > ds3[u]){
                continue;
            }
            ans = min(ans, w + d[3][u]);

            for(int v : dag[u]){
                long long c = min(w, d[3][u]);
                if(c < ds3[v]){
                    ds3[v] = c;
                    q.push({-c, v});
                }
            }
        }

        // for(int i=1;i<=n;++i){
        //     ans = min({ans, dp[1][i] + d[4][i], dp[2][i] + d[3][i]});
        // }
        cout<<ans;
    }
}

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, 63, 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();
    }
    SUB3::solve();

    return 0;
}

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