oj.uz

답안 #944145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944145 2024-03-12T09:03:09 Z tnknguyen_ Commuter Pass (JOI18_commuter_pass) C++14
40 / 100
 230 ms 28036 KB 
#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);
        }
    }

    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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 25284 KB Output is correct
2 Correct 181 ms 24052 KB Output is correct
3 Correct 158 ms 25180 KB Output is correct
4 Correct 163 ms 25288 KB Output is correct
5 Correct 228 ms 24136 KB Output is correct
6 Correct 173 ms 25404 KB Output is correct
7 Correct 169 ms 23944 KB Output is correct
8 Correct 175 ms 24076 KB Output is correct
9 Correct 220 ms 24056 KB Output is correct
10 Correct 160 ms 23876 KB Output is correct
11 Correct 66 ms 17104 KB Output is correct
12 Correct 204 ms 24068 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 28036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 13424 KB Output is correct
2 Correct 28 ms 11868 KB Output is correct
3 Correct 32 ms 12112 KB Output is correct
4 Correct 36 ms 14684 KB Output is correct
5 Correct 34 ms 13404 KB Output is correct
6 Correct 29 ms 12120 KB Output is correct
7 Correct 28 ms 12124 KB Output is correct
8 Correct 28 ms 12124 KB Output is correct
9 Correct 27 ms 12120 KB Output is correct
10 Correct 32 ms 13404 KB Output is correct
11 Correct 27 ms 11864 KB Output is correct
12 Correct 27 ms 12048 KB Output is correct
13 Correct 27 ms 11876 KB Output is correct
14 Correct 31 ms 11936 KB Output is correct
15 Correct 27 ms 11864 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 25284 KB Output is correct
2 Correct 181 ms 24052 KB Output is correct
3 Correct 158 ms 25180 KB Output is correct
4 Correct 163 ms 25288 KB Output is correct
5 Correct 228 ms 24136 KB Output is correct
6 Correct 173 ms 25404 KB Output is correct
7 Correct 169 ms 23944 KB Output is correct
8 Correct 175 ms 24076 KB Output is correct
9 Correct 220 ms 24056 KB Output is correct
10 Correct 160 ms 23876 KB Output is correct
11 Correct 66 ms 17104 KB Output is correct
12 Correct 204 ms 24068 KB Output is correct
13 Incorrect 230 ms 28036 KB Output isn't correct
14 Halted 0 ms 0 KB -