oj.uz

Submission #683687

# Submission time Handle Problem Language Result Execution time Memory
683687 2023-01-19T05:34:10 Z yogesh_sane Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 390 ms 23820 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;
int n, m, s, t, u, v;

vector<vector<pair<int, int>>> adj;
vector<long long>distU, distV, dpU, dpV;
long long const INF = 1e15;
long long ans = INF;

void dijkstras_ST(int start, int end){
    fill(dpU.begin(), dpU.end(), INF);
    fill(dpV.begin(), dpV.end(), INF);
    vector<bool> visited(n+1, false);
    priority_queue<tuple<long long, int, int>> q;       //dist, node, parent
    vector<long long>dist(n+1,INF);
    q.push({0,start, 0});
    dist[start] = 0;
    while(!q.empty()){
        long long dist_node;
        int node, parent;
        tie(dist_node, node, parent) = q.top();
        dist_node *= -1;
        q.pop();
        if(!visited[node]){
            visited[node] = true;
            dist[node] = dist_node;
            dpU[node] = min(distU[node], dpU[parent]);
            dpV[node] = min(distV[node], dpV[parent]);
            for(auto edge : adj[node])
                q.push({-(dist[node]+edge.second),edge.first,node});
        }else if(dist_node == dist[node]){
            if(min(distU[node], dpU[parent]) + min(distV[node], dpV[parent]) <= dpU[node] + dpV[node]){
                dpU[node] = min(distU[node], dpU[parent]);
                dpV[node] = min(distV[node], dpV[parent]);
            }
        }
    }
    ans = min(ans, dpU[end] + dpV[end]);
}
void dijkstras_UV(int start, vector<long long> &dist){
    vector<bool> visited(n+1);
    priority_queue<pair<long long, int>> q;
    q.push({0,start});
    dist[start] = 0;
    while(!q.empty()){
        int node = q.top().second;
        q.pop();
        if(visited[node])
            continue;
        visited[node] = true;
        for(auto edge : adj[node]){
            int next = edge.first;
            int weight = edge.second;
            if(dist[node] + weight < dist[next]){
                dist[next] = dist[node] + weight;
                q.push({-dist[next],next});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("in.txt","r",stdin);
    cin >> n >> m >> s >> t >> u >> v;
    adj = vector<vector<pair<int, int>>>(n+1);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    distU = vector<long long>(n+1, INF);
    dijkstras_UV(u, distU);

    //base case, travel without pass
    ans = distU[v];    

    distV = vector<long long> (n+1, INF);
    dijkstras_UV(v, distV);

    dpU = vector<long long>(n+1);
    dpV = vector<long long>(n+1);
    dijkstras_ST(s,t);
    dijkstras_ST(t,s);
    cout << ans << '\n';
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 19672 KB Output is correct
2 Correct 361 ms 22792 KB Output is correct
3 Correct 318 ms 22612 KB Output is correct
4 Correct 390 ms 22932 KB Output is correct
5 Correct 301 ms 20380 KB Output is correct
6 Correct 378 ms 23276 KB Output is correct
7 Correct 334 ms 22636 KB Output is correct
8 Correct 329 ms 22808 KB Output is correct
9 Correct 368 ms 23740 KB Output is correct
10 Correct 321 ms 23736 KB Output is correct
11 Correct 105 ms 11704 KB Output is correct
12 Correct 357 ms 23816 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 19584 KB Output is correct
2 Correct 319 ms 16876 KB Output is correct
3 Correct 361 ms 22376 KB Output is correct
4 Correct 328 ms 20484 KB Output is correct
5 Correct 355 ms 20184 KB Output is correct
6 Correct 366 ms 22904 KB Output is correct
7 Correct 305 ms 20144 KB Output is correct
8 Correct 367 ms 20348 KB Output is correct
9 Correct 314 ms 20204 KB Output is correct
10 Correct 324 ms 22436 KB Output is correct
11 Correct 102 ms 11836 KB Output is correct
12 Correct 350 ms 22632 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1788 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 41 ms 4100 KB Output is correct
5 Correct 23 ms 2884 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 22 ms 2960 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 19672 KB Output is correct
2 Correct 361 ms 22792 KB Output is correct
3 Correct 318 ms 22612 KB Output is correct
4 Correct 390 ms 22932 KB Output is correct
5 Correct 301 ms 20380 KB Output is correct
6 Correct 378 ms 23276 KB Output is correct
7 Correct 334 ms 22636 KB Output is correct
8 Correct 329 ms 22808 KB Output is correct
9 Correct 368 ms 23740 KB Output is correct
10 Correct 321 ms 23736 KB Output is correct
11 Correct 105 ms 11704 KB Output is correct
12 Correct 357 ms 23816 KB Output is correct
13 Correct 336 ms 19584 KB Output is correct
14 Correct 319 ms 16876 KB Output is correct
15 Correct 361 ms 22376 KB Output is correct
16 Correct 328 ms 20484 KB Output is correct
17 Correct 355 ms 20184 KB Output is correct
18 Correct 366 ms 22904 KB Output is correct
19 Correct 305 ms 20144 KB Output is correct
20 Correct 367 ms 20348 KB Output is correct
21 Correct 314 ms 20204 KB Output is correct
22 Correct 324 ms 22436 KB Output is correct
23 Correct 102 ms 11836 KB Output is correct
24 Correct 350 ms 22632 KB Output is correct
25 Correct 19 ms 1788 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 41 ms 4100 KB Output is correct
29 Correct 23 ms 2884 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 456 KB Output is correct
32 Correct 4 ms 596 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 22 ms 2960 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 320 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 340 ms 23640 KB Output is correct
41 Correct 367 ms 23792 KB Output is correct
42 Correct 359 ms 23820 KB Output is correct
43 Correct 127 ms 11848 KB Output is correct
44 Correct 103 ms 11844 KB Output is correct
45 Correct 335 ms 19532 KB Output is correct
46 Correct 315 ms 19092 KB Output is correct
47 Correct 346 ms 20512 KB Output is correct
48 Correct 111 ms 11240 KB Output is correct
49 Correct 324 ms 22492 KB Output is correct
50 Correct 335 ms 19388 KB Output is correct
51 Correct 346 ms 19292 KB Output is correct