Submission #944156

#	Time	Username	Problem	Language	Result	Execution time	Memory
944156		tnknguyen_	Commuter Pass (JOI18_commuter_pass)	C++14	40 / 100	266 ms	29532 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);
//             }
//         }
//     }
// }
 
// 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);
//         }
//     }
// }
 
// // ------------- 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];
//         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;
// }

#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[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[3][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