제출 #944171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944171		tnknguyen_	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	275 ms	31040 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);
            }
        }
    }
}

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);
}
 
// ------------- 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]; //U -> i
            dp[2][i] = d[4][i]; //V -> i
        }
 
        topo(S);

        for(int u : tp){
            for(int v : dag[u]){
                dp[1][v] = min(dp[1][v], dp[1][u]);
                dp[2][v] = min(dp[2][v], dp[2][u]);
            }
        }

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

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