oj.uz

Submission #948497

# Submission time Handle Problem Language Result Execution time Memory
948497 2024-03-18T07:07:52 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 47004 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(vector<vector<pair<ll, ll>>> g){
    //reset();
    memset(vis, 0, sizeof(vis));
    pq.push({0, u});
    dis[u] = 0;
    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){
                dis[e] = dis[now] + w;
                pq.push({dis[e], e});
            }
        }
    }

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

void solve(int d){
    if(d == s) cal(G);
    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';
    // }
    
    reset();
    solve(t);

    cout << ans;

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 32704 KB Output is correct
2 Execution timed out 2048 ms 32924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 37940 KB Output is correct
2 Correct 220 ms 38856 KB Output is correct
3 Correct 259 ms 37688 KB Output is correct
4 Correct 201 ms 38588 KB Output is correct
5 Correct 225 ms 39680 KB Output is correct
6 Correct 220 ms 43600 KB Output is correct
7 Correct 230 ms 47004 KB Output is correct
8 Correct 203 ms 38716 KB Output is correct
9 Correct 268 ms 39548 KB Output is correct
10 Correct 219 ms 38036 KB Output is correct
11 Correct 122 ms 34612 KB Output is correct
12 Correct 272 ms 44228 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 32704 KB Output is correct
2 Execution timed out 2048 ms 32924 KB Time limit exceeded
3 Halted 0 ms 0 KB -