oj.uz

Submission #478074

# Submission time Handle Problem Language Result Execution time Memory
478074 2021-10-05T13:57:01 Z FireGhost1301 Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 317 ms 27480 KB 
/**
    __author__: FireGhost
*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define fi first
#define se second

const int N = 1e5 + 3;
int n, m, S, T, U, V;
vector<pii> g[N];
ll dS[N], dU[N], dV[N];
vector<int> prv[N], nxt[N];
bool vst[N];
ll dp[N], dp2[N];

void dijkstra(int s, ll* d) {
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    d[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto x = pq.top(); pq.pop();
        int u = x.se; 
        ll dist = x.fi;
        if (dist != d[u]) continue;
        for (pair<int, int> e: g[u]) {
            int v = e.fi, w = e.se;
            if (d[v] > dist + w) {
                d[v] = dist + w;
                pq.emplace(d[v], v);
                if (s == S) {
                    prv[v].clear();
                    prv[v].push_back(u);
                }
            }
            else if (s == S && d[v] == dist + w) prv[v].push_back(u);
        }
    }
}

void dfs(int u) {
    vst[u] = true;
    for (int v: prv[u]) {
        nxt[v].push_back(u);
        if (!vst[v]) dfs(v);
    }
}

void dfs_dp(int u) {
    dp[u] = dV[u];
    for (int v: nxt[u]) {
        if (dp[v] == LLONG_MAX) dfs_dp(v);
        dp[u] = min(dp[u], dp[v]);
    }
}

void dfs_dp2(int u) {
    dp2[u] = dV[u];
    for (int v: prv[u]) {
        if (dp2[v] == LLONG_MAX) dfs_dp2(v);
        dp2[u] = min(dp2[u], dp2[v]);
    }
}

void init() {
    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
}

void solve() {
    init();

    memset(dS, 0x3f, sizeof dS);
    memset(dU, 0x3f, sizeof dU), memset(dV, 0x3f, sizeof dV);
    dijkstra(S, dS);
    dijkstra(U, dU), dijkstra(V, dV);
    dfs(T);

    for (int i = 1; i <= n; ++i) {
        dp[i] = dp2[i] = LLONG_MAX;
        if (!vst[i]) prv[i].clear();
    }
    dfs_dp(S);
    dfs_dp2(T);

    ll ans = dU[V];
    for (int i = 1; i <= n; ++i) {
        if (!vst[i]) continue;
        ans = min(ans, dU[i] + min(dp[i], dp2[i]));
    }

    cout << ans;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 21772 KB Output is correct
2 Correct 275 ms 21636 KB Output is correct
3 Correct 292 ms 27440 KB Output is correct
4 Correct 265 ms 21708 KB Output is correct
5 Correct 298 ms 22000 KB Output is correct
6 Correct 260 ms 21772 KB Output is correct
7 Correct 293 ms 22412 KB Output is correct
8 Correct 288 ms 22204 KB Output is correct
9 Correct 274 ms 20432 KB Output is correct
10 Correct 227 ms 20340 KB Output is correct
11 Correct 134 ms 22096 KB Output is correct
12 Correct 279 ms 20484 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 23192 KB Output is correct
2 Correct 296 ms 23684 KB Output is correct
3 Correct 291 ms 23112 KB Output is correct
4 Correct 307 ms 23516 KB Output is correct
5 Correct 317 ms 24352 KB Output is correct
6 Correct 311 ms 26720 KB Output is correct
7 Correct 301 ms 27480 KB Output is correct
8 Correct 315 ms 23580 KB Output is correct
9 Correct 280 ms 24216 KB Output is correct
10 Correct 290 ms 23432 KB Output is correct
11 Correct 125 ms 24472 KB Output is correct
12 Correct 278 ms 27152 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10444 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 24 ms 11064 KB Output is correct
5 Correct 13 ms 10444 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9728 KB Output is correct
8 Correct 7 ms 9804 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 13 ms 10416 KB Output is correct
11 Correct 5 ms 9676 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 5 ms 9676 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 21772 KB Output is correct
2 Correct 275 ms 21636 KB Output is correct
3 Correct 292 ms 27440 KB Output is correct
4 Correct 265 ms 21708 KB Output is correct
5 Correct 298 ms 22000 KB Output is correct
6 Correct 260 ms 21772 KB Output is correct
7 Correct 293 ms 22412 KB Output is correct
8 Correct 288 ms 22204 KB Output is correct
9 Correct 274 ms 20432 KB Output is correct
10 Correct 227 ms 20340 KB Output is correct
11 Correct 134 ms 22096 KB Output is correct
12 Correct 279 ms 20484 KB Output is correct
13 Correct 269 ms 23192 KB Output is correct
14 Correct 296 ms 23684 KB Output is correct
15 Correct 291 ms 23112 KB Output is correct
16 Correct 307 ms 23516 KB Output is correct
17 Correct 317 ms 24352 KB Output is correct
18 Correct 311 ms 26720 KB Output is correct
19 Correct 301 ms 27480 KB Output is correct
20 Correct 315 ms 23580 KB Output is correct
21 Correct 280 ms 24216 KB Output is correct
22 Correct 290 ms 23432 KB Output is correct
23 Correct 125 ms 24472 KB Output is correct
24 Correct 278 ms 27152 KB Output is correct
25 Correct 12 ms 10444 KB Output is correct
26 Correct 5 ms 9676 KB Output is correct
27 Correct 5 ms 9676 KB Output is correct
28 Correct 24 ms 11064 KB Output is correct
29 Correct 13 ms 10444 KB Output is correct
30 Correct 7 ms 9676 KB Output is correct
31 Correct 7 ms 9728 KB Output is correct
32 Correct 7 ms 9804 KB Output is correct
33 Correct 6 ms 9676 KB Output is correct
34 Correct 13 ms 10416 KB Output is correct
35 Correct 5 ms 9676 KB Output is correct
36 Correct 5 ms 9676 KB Output is correct
37 Correct 5 ms 9696 KB Output is correct
38 Correct 6 ms 9676 KB Output is correct
39 Correct 5 ms 9676 KB Output is correct
40 Correct 246 ms 21912 KB Output is correct
41 Correct 235 ms 20440 KB Output is correct
42 Correct 263 ms 20436 KB Output is correct
43 Correct 141 ms 24648 KB Output is correct
44 Correct 147 ms 24656 KB Output is correct
45 Correct 313 ms 23568 KB Output is correct
46 Correct 298 ms 23660 KB Output is correct
47 Correct 267 ms 21648 KB Output is correct
48 Correct 127 ms 22328 KB Output is correct
49 Correct 229 ms 22048 KB Output is correct
50 Correct 303 ms 22836 KB Output is correct
51 Correct 296 ms 23576 KB Output is correct