oj.uz

Submission #926783

# Submission time Handle Problem Language Result Execution time Memory
926783 2024-02-13T17:41:52 Z LonlyR Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 211 ms 42140 KB 
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 2e5 + 5;
int n, m, s, t, a, b, ans = 1e18;
int d[4][maxn], vis[maxn];
ii dp[maxn];
vector<ii> adj[maxn];
vector<int> dag[maxn];

void bfs(int x) /// dijkstra
{
    int y;
    if (x == t) y = 1;
    else if (x == a) y = 2;
    else y = 3;
    memset(d[y], 0x3f, sizeof d[y]);
    d[y][x] = 0;
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.emplace(0, x);
    while (pq.size())
    {
        int u, v;
        tie(v, u) = pq.top();
        pq.pop();
        if (v != d[y][u]) continue;
        for (auto p : adj[u])
            if (d[y][p.ff] > v + p.ss)
                pq.emplace(d[y][p.ff] = v + p.ss, p.ff);
    }
}

void dfs(int x)
{
    if (vis[x]) return;
    vis[x] = 1;
    for (auto p : adj[x])
        if (d[1][x] == d[1][p.ff] + p.ss)
            dag[x].emplace_back(p.ff),
            dfs(p.ff);
}

ii cal(int x)
{
    if (vis[x]) return dp[x];
    vis[x] = 1;
    dp[x].ff = d[3][x];
    dp[x].ss = d[2][x];
    for (int i : dag[x])
    {
        int u, v;
        tie(u, v) = cal(i);
        dp[x].ff = min(dp[x].ff, u);
        dp[x].ss = min(dp[x].ss, v);
    }
    ans = min(ans, d[2][x] + dp[x].ff);
    ans = min(ans, d[3][x] + dp[x].ss);
    return dp[x];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m >> s >> t >> a >> b;
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w,
        adj[u].emplace_back(v, w),
        adj[v].emplace_back(u, w);
    bfs(t);
    bfs(a);
    bfs(b);
    dfs(s);
    memset(vis, 0, sizeof vis);
    cal(s);
    ans = min(ans, d[2][b]);
    cout << ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 30760 KB Output is correct
2 Correct 176 ms 34296 KB Output is correct
3 Correct 184 ms 42140 KB Output is correct
4 Correct 148 ms 34352 KB Output is correct
5 Correct 174 ms 35068 KB Output is correct
6 Correct 171 ms 34416 KB Output is correct
7 Correct 175 ms 35460 KB Output is correct
8 Correct 179 ms 35156 KB Output is correct
9 Correct 162 ms 34956 KB Output is correct
10 Correct 129 ms 35068 KB Output is correct
11 Correct 65 ms 32336 KB Output is correct
12 Correct 168 ms 34828 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 33424 KB Output is correct
2 Correct 178 ms 34016 KB Output is correct
3 Correct 179 ms 33212 KB Output is correct
4 Correct 199 ms 34360 KB Output is correct
5 Correct 179 ms 34476 KB Output is correct
6 Correct 200 ms 37236 KB Output is correct
7 Correct 208 ms 38576 KB Output is correct
8 Correct 200 ms 33944 KB Output is correct
9 Correct 177 ms 34464 KB Output is correct
10 Correct 199 ms 33388 KB Output is correct
11 Correct 75 ms 32984 KB Output is correct
12 Correct 191 ms 37948 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19548 KB Output is correct
2 Correct 5 ms 18524 KB Output is correct
3 Correct 6 ms 18524 KB Output is correct
4 Correct 14 ms 21564 KB Output is correct
5 Correct 10 ms 19804 KB Output is correct
6 Correct 5 ms 18352 KB Output is correct
7 Correct 5 ms 18268 KB Output is correct
8 Correct 5 ms 18524 KB Output is correct
9 Correct 6 ms 18344 KB Output is correct
10 Correct 10 ms 19804 KB Output is correct
11 Correct 4 ms 18200 KB Output is correct
12 Correct 4 ms 18264 KB Output is correct
13 Correct 7 ms 18088 KB Output is correct
14 Correct 4 ms 18268 KB Output is correct
15 Correct 4 ms 18268 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 30760 KB Output is correct
2 Correct 176 ms 34296 KB Output is correct
3 Correct 184 ms 42140 KB Output is correct
4 Correct 148 ms 34352 KB Output is correct
5 Correct 174 ms 35068 KB Output is correct
6 Correct 171 ms 34416 KB Output is correct
7 Correct 175 ms 35460 KB Output is correct
8 Correct 179 ms 35156 KB Output is correct
9 Correct 162 ms 34956 KB Output is correct
10 Correct 129 ms 35068 KB Output is correct
11 Correct 65 ms 32336 KB Output is correct
12 Correct 168 ms 34828 KB Output is correct
13 Correct 172 ms 33424 KB Output is correct
14 Correct 178 ms 34016 KB Output is correct
15 Correct 179 ms 33212 KB Output is correct
16 Correct 199 ms 34360 KB Output is correct
17 Correct 179 ms 34476 KB Output is correct
18 Correct 200 ms 37236 KB Output is correct
19 Correct 208 ms 38576 KB Output is correct
20 Correct 200 ms 33944 KB Output is correct
21 Correct 177 ms 34464 KB Output is correct
22 Correct 199 ms 33388 KB Output is correct
23 Correct 75 ms 32984 KB Output is correct
24 Correct 191 ms 37948 KB Output is correct
25 Correct 9 ms 19548 KB Output is correct
26 Correct 5 ms 18524 KB Output is correct
27 Correct 6 ms 18524 KB Output is correct
28 Correct 14 ms 21564 KB Output is correct
29 Correct 10 ms 19804 KB Output is correct
30 Correct 5 ms 18352 KB Output is correct
31 Correct 5 ms 18268 KB Output is correct
32 Correct 5 ms 18524 KB Output is correct
33 Correct 6 ms 18344 KB Output is correct
34 Correct 10 ms 19804 KB Output is correct
35 Correct 4 ms 18200 KB Output is correct
36 Correct 4 ms 18264 KB Output is correct
37 Correct 7 ms 18088 KB Output is correct
38 Correct 4 ms 18268 KB Output is correct
39 Correct 4 ms 18268 KB Output is correct
40 Correct 183 ms 33756 KB Output is correct
41 Correct 162 ms 34696 KB Output is correct
42 Correct 195 ms 34928 KB Output is correct
43 Correct 84 ms 35116 KB Output is correct
44 Correct 89 ms 35180 KB Output is correct
45 Correct 211 ms 37124 KB Output is correct
46 Correct 180 ms 36704 KB Output is correct
47 Correct 188 ms 34316 KB Output is correct
48 Correct 76 ms 31316 KB Output is correct
49 Correct 153 ms 34148 KB Output is correct
50 Correct 192 ms 36168 KB Output is correct
51 Correct 169 ms 37024 KB Output is correct