# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
769452 | 2023-06-29T15:12:10 Z | Alora | Commuter Pass (JOI18_commuter_pass) | C++17 | 267 ms | 32304 KB |
#include <bits/stdc++.h> #define name "cownav" #define fi(i,a,b) for(int i = a; i <= b; i++) #define fid(i,a,b) for(int i = a; i >= b; i--) #define ll long long #define int long long #define f first #define se second #define pii pair<ll, int> #define getbit(i, j) ((i >> j) & 1) #define pb push_back #define all(v) v.begin(), v.end() #define maxn 200005 const int M = 1e9 + 7; using namespace std; int n, m, S, T, U, V; vector <pii> g[maxn]; vector <vector<ll>> dp(5, vector<ll>(maxn, 1e18)); void dij(int x, vector <ll> &L){ L[x] = 0; priority_queue <pii> q; q.push({0, x}); while(q.size()){ ll h = -q.top().f; int u = q.top().se; q.pop(); if(h != L[u]) continue; for(auto e: g[u]){ int v = e.f, w = e.se; if(L[v] > L[u] + w){ L[v] = L[u] + w; q.push({-L[v], v}); } } } } ll L[maxn], ans = 1e18; ll sol(int u, ll d, int x){ if(d + dp[1][u] != dp[0][T]) return 1e18; if(L[u] != -1) return L[u]; ll tmp = dp[5 - x][u]; for(auto e: g[u]){ int v = e.f, w = e.se; tmp = min(tmp, sol(v, dp[0][u] + w, x)); } ans = min(ans, dp[x][u] + tmp); return L[u] = tmp; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); //freopen(name".in", "r", stdin); // freopen(name".out", "w", stdout); cin >> n >> m; cin >> S >> T >> U >> V; fi(i, 1, m){ int u, v, z; cin >> u >> v >> z; g[u].pb({v, z}); g[v].pb({u, z}); } dij(S, dp[0]); dij(T, dp[1]); dij(U, dp[2]); dij(V, dp[3]); ans = dp[2][V]; fi(i, 1, n) L[i] = -1; sol(S, 0, 2); fi(i, 1, n) L[i] = -1; sol(S, 0, 3); cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 226 ms | 27164 KB | Output is correct |
2 | Correct | 212 ms | 27180 KB | Output is correct |
3 | Correct | 253 ms | 32304 KB | Output is correct |
4 | Correct | 185 ms | 27380 KB | Output is correct |
5 | Correct | 209 ms | 27104 KB | Output is correct |
6 | Correct | 230 ms | 27564 KB | Output is correct |
7 | Correct | 244 ms | 27296 KB | Output is correct |
8 | Correct | 210 ms | 27276 KB | Output is correct |
9 | Correct | 191 ms | 26988 KB | Output is correct |
10 | Correct | 187 ms | 26804 KB | Output is correct |
11 | Correct | 75 ms | 23192 KB | Output is correct |
12 | Correct | 220 ms | 27052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 224 ms | 28972 KB | Output is correct |
2 | Correct | 213 ms | 29172 KB | Output is correct |
3 | Correct | 222 ms | 28736 KB | Output is correct |
4 | Correct | 219 ms | 29444 KB | Output is correct |
5 | Correct | 216 ms | 29944 KB | Output is correct |
6 | Correct | 267 ms | 31768 KB | Output is correct |
7 | Correct | 229 ms | 32172 KB | Output is correct |
8 | Correct | 227 ms | 29568 KB | Output is correct |
9 | Correct | 259 ms | 30020 KB | Output is correct |
10 | Correct | 240 ms | 29148 KB | Output is correct |
11 | Correct | 99 ms | 24888 KB | Output is correct |
12 | Correct | 236 ms | 32148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 14648 KB | Output is correct |
2 | Correct | 7 ms | 14292 KB | Output is correct |
3 | Correct | 7 ms | 14292 KB | Output is correct |
4 | Correct | 21 ms | 16260 KB | Output is correct |
5 | Correct | 12 ms | 14520 KB | Output is correct |
6 | Correct | 8 ms | 14292 KB | Output is correct |
7 | Correct | 10 ms | 14292 KB | Output is correct |
8 | Correct | 8 ms | 14292 KB | Output is correct |
9 | Correct | 7 ms | 14292 KB | Output is correct |
10 | Correct | 11 ms | 14520 KB | Output is correct |
11 | Correct | 6 ms | 14292 KB | Output is correct |
12 | Correct | 7 ms | 14292 KB | Output is correct |
13 | Correct | 6 ms | 14292 KB | Output is correct |
14 | Correct | 7 ms | 14292 KB | Output is correct |
15 | Correct | 7 ms | 14340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 226 ms | 27164 KB | Output is correct |
2 | Correct | 212 ms | 27180 KB | Output is correct |
3 | Correct | 253 ms | 32304 KB | Output is correct |
4 | Correct | 185 ms | 27380 KB | Output is correct |
5 | Correct | 209 ms | 27104 KB | Output is correct |
6 | Correct | 230 ms | 27564 KB | Output is correct |
7 | Correct | 244 ms | 27296 KB | Output is correct |
8 | Correct | 210 ms | 27276 KB | Output is correct |
9 | Correct | 191 ms | 26988 KB | Output is correct |
10 | Correct | 187 ms | 26804 KB | Output is correct |
11 | Correct | 75 ms | 23192 KB | Output is correct |
12 | Correct | 220 ms | 27052 KB | Output is correct |
13 | Correct | 224 ms | 28972 KB | Output is correct |
14 | Correct | 213 ms | 29172 KB | Output is correct |
15 | Correct | 222 ms | 28736 KB | Output is correct |
16 | Correct | 219 ms | 29444 KB | Output is correct |
17 | Correct | 216 ms | 29944 KB | Output is correct |
18 | Correct | 267 ms | 31768 KB | Output is correct |
19 | Correct | 229 ms | 32172 KB | Output is correct |
20 | Correct | 227 ms | 29568 KB | Output is correct |
21 | Correct | 259 ms | 30020 KB | Output is correct |
22 | Correct | 240 ms | 29148 KB | Output is correct |
23 | Correct | 99 ms | 24888 KB | Output is correct |
24 | Correct | 236 ms | 32148 KB | Output is correct |
25 | Correct | 12 ms | 14648 KB | Output is correct |
26 | Correct | 7 ms | 14292 KB | Output is correct |
27 | Correct | 7 ms | 14292 KB | Output is correct |
28 | Correct | 21 ms | 16260 KB | Output is correct |
29 | Correct | 12 ms | 14520 KB | Output is correct |
30 | Correct | 8 ms | 14292 KB | Output is correct |
31 | Correct | 10 ms | 14292 KB | Output is correct |
32 | Correct | 8 ms | 14292 KB | Output is correct |
33 | Correct | 7 ms | 14292 KB | Output is correct |
34 | Correct | 11 ms | 14520 KB | Output is correct |
35 | Correct | 6 ms | 14292 KB | Output is correct |
36 | Correct | 7 ms | 14292 KB | Output is correct |
37 | Correct | 6 ms | 14292 KB | Output is correct |
38 | Correct | 7 ms | 14292 KB | Output is correct |
39 | Correct | 7 ms | 14340 KB | Output is correct |
40 | Correct | 178 ms | 26556 KB | Output is correct |
41 | Correct | 182 ms | 26512 KB | Output is correct |
42 | Correct | 182 ms | 26540 KB | Output is correct |
43 | Correct | 115 ms | 23364 KB | Output is correct |
44 | Correct | 87 ms | 23428 KB | Output is correct |
45 | Correct | 198 ms | 26240 KB | Output is correct |
46 | Correct | 206 ms | 26156 KB | Output is correct |
47 | Correct | 203 ms | 26868 KB | Output is correct |
48 | Correct | 87 ms | 20784 KB | Output is correct |
49 | Correct | 169 ms | 26580 KB | Output is correct |
50 | Correct | 188 ms | 26304 KB | Output is correct |
51 | Correct | 207 ms | 26284 KB | Output is correct |