oj.uz

Submission #948600

# Submission time Handle Problem Language Result Execution time Memory
948600 2024-03-18T08:31:07 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 153556 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();

        if(now == v) {
            ans = min(ans, dis[v]);
            return;
        }

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

}

void solve(int d){
    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();
        }
    }   
}

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 154 ms 26052 KB Output is correct
2 Execution timed out 2075 ms 153556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 27072 KB Output is correct
2 Correct 168 ms 30520 KB Output is correct
3 Correct 153 ms 30152 KB Output is correct
4 Correct 131 ms 29892 KB Output is correct
5 Correct 209 ms 32712 KB Output is correct
6 Correct 195 ms 36292 KB Output is correct
7 Correct 145 ms 36804 KB Output is correct
8 Correct 208 ms 31428 KB Output is correct
9 Correct 151 ms 31940 KB Output is correct
10 Correct 128 ms 26820 KB Output is correct
11 Correct 96 ms 26312 KB Output is correct
12 Correct 201 ms 37572 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 26052 KB Output is correct
2 Execution timed out 2075 ms 153556 KB Time limit exceeded
3 Halted 0 ms 0 KB -