oj.uz

Submission #949133

# Submission time Handle Problem Language Result Execution time Memory
949133 2024-03-19T01:56:08 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 35012 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

ll n, m, s, t, u, v, ans = 1e18, dis[100001];
vector<vector<pair<ll, ll>>> G(100001);
vector<int> E[100001], par[100001];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
bool vis[100001];

void reset() { for(int i = 1; i <= n; i++) dis[i] = LLONG_MAX; }

void cal(){
    reset();

    pq.push({0, u});
    dis[u] = 0;
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();

        for(auto &[e, w] : G[now]){
            if(dis[e] > dis[now] + w){
                dis[e] = dis[now] + w;
                pq.push({dis[e], e});
            }
        }
    }

    ans = min(ans, dis[v]);
}

void solve(int d){
    int tmp = d;
    while(d != s && par[d].size() == 1){
        int e = par[d][0];
        G[d].push_back({e, 0});
        G[e].push_back({d, 0});
        d = e;
    }

    if(d == s) {
        cal(); 
    }else {
        for(auto &e : par[d]){
            G[d].push_back({e, 0});
            G[e].push_back({d, 0});
            solve(e);
            G[d].pop_back();
            G[e].pop_back();
        }
    }

    d = tmp;
    while(d != s && par[d].size() == 1){
        int e = par[d][0];
        G[d].pop_back();
        G[e].pop_back();
        d = e;
    }   
}

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

    cin >> n >> m >> s >> t >> u >> v;
    for(ll i = 0; i < m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    reset();

    pq.push({0, s});
    dis[s] = 0;
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();

        if(now == t) break;

        for(auto &[e, w] : G[now]){
            if(dis[e] > dis[now] + w){
                dis[e] = dis[now] + w;
                pq.push({dis[e], e});
            }
        }
    }   

    pq.push({0, s});
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();   

        if(now == t) break;
        if(vis[now]) continue;
        vis[now] = 1;
        for(auto &[e, w] : G[now]){
            if(dis[e] == dis[now] + w){
                par[e].push_back(now); 
                pq.push({dis[e], e});
            }
        }
    }  

    
    // for(int i = 1; i <= n; i++){
    //     cout << "i: " << i << '\n';
    //     for(auto &e : par[i]) cout << e << ' ';
    //     cout << '\n';
    // }

    reset();
    solve(t);   

    cout << ans;

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 29248 KB Output is correct
2 Execution timed out 2062 ms 29860 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 32208 KB Output is correct
2 Correct 227 ms 31252 KB Output is correct
3 Correct 193 ms 31544 KB Output is correct
4 Correct 187 ms 32116 KB Output is correct
5 Correct 208 ms 32280 KB Output is correct
6 Correct 211 ms 34384 KB Output is correct
7 Correct 202 ms 33356 KB Output is correct
8 Correct 212 ms 30720 KB Output is correct
9 Correct 218 ms 32700 KB Output is correct
10 Correct 184 ms 30916 KB Output is correct
11 Correct 91 ms 22292 KB Output is correct
12 Correct 209 ms 35012 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 9308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 29248 KB Output is correct
2 Execution timed out 2062 ms 29860 KB Time limit exceeded
3 Halted 0 ms 0 KB -