oj.uz

Submission #703067

# Submission time Handle Problem Language Result Execution time Memory
703067 2023-02-25T21:08:02 Z speedyArda Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 643 ms 31536 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
const ll INF = 1e18;
bool visited[MAXN];
ll dpU[MAXN], dpV[MAXN], dp[2][MAXN], dpS[MAXN], ans = 2e18;
//int par[MAXN];
vector< vector< pair<long long, long long > > > adj(MAXN);

void dijkstra1(int v, ll arr[])
{
    fill(visited, visited + MAXN, false);
    priority_queue< pair<ll, ll > > pq;
    pq.push({0LL, v});
    while(!pq.empty())
    {
        pair<ll, ll> curr = pq.top();   
        pq.pop();
        if(!visited[curr.second])
        {
            arr[curr.second] = -curr.first;
            visited[curr.second] = true;
            for(pair<ll, ll>  e : adj[curr.second])
                pq.push({curr.first - e.first, e.second});
        }
    }
}

void dijkstra2(int start, int end)
{
    fill(dp[0], dp[0] + MAXN,  INF);
    fill(dp[1], dp[1] + MAXN, INF);
    fill(visited, visited + MAXN, false);
    priority_queue< pair<ll, pair<ll, ll> > > pq;
    pq.push({0, {start, 0}});
    dp[0][0] = dp[1][0] = INF;
    while(!pq.empty())
    {
        pair<ll, pair<ll, ll> > curr = pq.top();
        pq.pop();
        ll node = curr.second.first;
        ll dist = curr.first;
        ll par = curr.second.second;
        if(!visited[node])
        {
            dpS[node] = -dist;
            visited[node] = true;
            dp[0][node] = min(dp[0][par], dpU[node]);
            dp[1][node] = min(dp[1][par], dpV[node]);
            for(pair<ll, ll> e : adj[node])
            {
                pq.push({dist - e.first, {e.second, node}});
            }
        } else if(dpS[node] == -dist)
        {
            if(min(dpU[node], dp[0][par]) + min(dpV[node], dp[1][par]) <= dp[0][node] + dp[1][node]) {
                dp[0][node] = min(dp[0][par], dpU[node]);
                dp[1][node] = min(dp[1][par], dpV[node]);
            }
        }

    }

    ans = min(ans, dp[0][end] + dp[1][end]);
}

int main() 
{

    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    
    dijkstra1(u, dpU);
    dijkstra1(v, dpV);

    ans = dpU[v];
    
    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << "\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 31064 KB Output is correct
2 Correct 527 ms 30260 KB Output is correct
3 Correct 523 ms 30044 KB Output is correct
4 Correct 570 ms 30144 KB Output is correct
5 Correct 518 ms 26392 KB Output is correct
6 Correct 584 ms 31076 KB Output is correct
7 Correct 510 ms 29980 KB Output is correct
8 Correct 523 ms 30312 KB Output is correct
9 Correct 575 ms 31536 KB Output is correct
10 Correct 576 ms 31472 KB Output is correct
11 Correct 182 ms 13888 KB Output is correct
12 Correct 568 ms 31448 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 30708 KB Output is correct
2 Correct 503 ms 26560 KB Output is correct
3 Correct 500 ms 29916 KB Output is correct
4 Correct 513 ms 26552 KB Output is correct
5 Correct 517 ms 26452 KB Output is correct
6 Correct 514 ms 29888 KB Output is correct
7 Correct 507 ms 26564 KB Output is correct
8 Correct 546 ms 26600 KB Output is correct
9 Correct 500 ms 26336 KB Output is correct
10 Correct 521 ms 29788 KB Output is correct
11 Correct 190 ms 13904 KB Output is correct
12 Correct 526 ms 30068 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7516 KB Output is correct
2 Correct 4 ms 4308 KB Output is correct
3 Correct 4 ms 4308 KB Output is correct
4 Correct 89 ms 10600 KB Output is correct
5 Correct 46 ms 8440 KB Output is correct
6 Correct 5 ms 4436 KB Output is correct
7 Correct 6 ms 4564 KB Output is correct
8 Correct 8 ms 4724 KB Output is correct
9 Correct 5 ms 4464 KB Output is correct
10 Correct 45 ms 8340 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct
13 Correct 3 ms 4392 KB Output is correct
14 Correct 4 ms 4468 KB Output is correct
15 Correct 4 ms 4436 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 31064 KB Output is correct
2 Correct 527 ms 30260 KB Output is correct
3 Correct 523 ms 30044 KB Output is correct
4 Correct 570 ms 30144 KB Output is correct
5 Correct 518 ms 26392 KB Output is correct
6 Correct 584 ms 31076 KB Output is correct
7 Correct 510 ms 29980 KB Output is correct
8 Correct 523 ms 30312 KB Output is correct
9 Correct 575 ms 31536 KB Output is correct
10 Correct 576 ms 31472 KB Output is correct
11 Correct 182 ms 13888 KB Output is correct
12 Correct 568 ms 31448 KB Output is correct
13 Correct 581 ms 30708 KB Output is correct
14 Correct 503 ms 26560 KB Output is correct
15 Correct 500 ms 29916 KB Output is correct
16 Correct 513 ms 26552 KB Output is correct
17 Correct 517 ms 26452 KB Output is correct
18 Correct 514 ms 29888 KB Output is correct
19 Correct 507 ms 26564 KB Output is correct
20 Correct 546 ms 26600 KB Output is correct
21 Correct 500 ms 26336 KB Output is correct
22 Correct 521 ms 29788 KB Output is correct
23 Correct 190 ms 13904 KB Output is correct
24 Correct 526 ms 30068 KB Output is correct
25 Correct 46 ms 7516 KB Output is correct
26 Correct 4 ms 4308 KB Output is correct
27 Correct 4 ms 4308 KB Output is correct
28 Correct 89 ms 10600 KB Output is correct
29 Correct 46 ms 8440 KB Output is correct
30 Correct 5 ms 4436 KB Output is correct
31 Correct 6 ms 4564 KB Output is correct
32 Correct 8 ms 4724 KB Output is correct
33 Correct 5 ms 4464 KB Output is correct
34 Correct 45 ms 8340 KB Output is correct
35 Correct 3 ms 4308 KB Output is correct
36 Correct 3 ms 4308 KB Output is correct
37 Correct 3 ms 4392 KB Output is correct
38 Correct 4 ms 4468 KB Output is correct
39 Correct 4 ms 4436 KB Output is correct
40 Correct 586 ms 30892 KB Output is correct
41 Correct 583 ms 31252 KB Output is correct
42 Correct 643 ms 31316 KB Output is correct
43 Correct 182 ms 13932 KB Output is correct
44 Correct 182 ms 14028 KB Output is correct
45 Correct 511 ms 25080 KB Output is correct
46 Correct 520 ms 24860 KB Output is correct
47 Correct 589 ms 26688 KB Output is correct
48 Correct 163 ms 13332 KB Output is correct
49 Correct 576 ms 29308 KB Output is correct
50 Correct 503 ms 25172 KB Output is correct
51 Correct 493 ms 25060 KB Output is correct