oj.uz

Submission #948509

# Submission time Handle Problem Language Result Execution time Memory
948509 2024-03-18T07:17:42 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 153104 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) break;

        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){
    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();

        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(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';
    // }
    
    solve(t);

    cout << ans;

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 22208 KB Output is correct
2 Execution timed out 2065 ms 153104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 26564 KB Output is correct
2 Correct 206 ms 28360 KB Output is correct
3 Correct 168 ms 26284 KB Output is correct
4 Correct 141 ms 28088 KB Output is correct
5 Correct 196 ms 29152 KB Output is correct
6 Correct 209 ms 32896 KB Output is correct
7 Correct 167 ms 32716 KB Output is correct
8 Correct 190 ms 28400 KB Output is correct
9 Correct 151 ms 29128 KB Output is correct
10 Correct 151 ms 26404 KB Output is correct
11 Correct 107 ms 26312 KB Output is correct
12 Correct 187 ms 33480 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 22208 KB Output is correct
2 Execution timed out 2065 ms 153104 KB Time limit exceeded
3 Halted 0 ms 0 KB -