#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5;
const int64_t INF = 2e18L;
int n;
vector<pair<int, int>> g[1 + kN];
int64_t ans, du[1 + kN], dv[1 + kN];
void minSelf(int64_t &x, int64_t y) {
if (y < x) {
x = y;
}
}
void Dijkstra(int s, int64_t d[]) {
for (int v = 1; v <= n; ++v) {
d[v] = INF;
}
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
d[s] = 0;
pq.emplace(0, s);
while (!pq.empty()) {
int64_t cost;
int u;
tie(cost, u) = pq.top();
pq.pop();
if (cost != d[u]) {
continue;
}
for (auto it : g[u]) {
int v, w;
tie(v, w) = it;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.emplace(d[v], v);
}
}
}
}
void solve(int s, int t) {
/// drumul optim de la u la v poate sa intersecteze un drum continut intr-un drum de cost minim de la s la t
/// dp[node][0 / 1] =def= u si v se deplaseaza pana la cate un nod de pe un ACELASI drum de cost
/// minim de la s la node astfel incat dp[node][0] + dp[node][1] este minim(ma intereseaza doar cat
/// au de facut pana la nodurile respective pentru ca intre ele folosesc commuter-ul si va fi gratis)
/// in timp ce fac drumul minim de la s la t actualizez dinamica
vector<int64_t> d(n + 1, INF);
vector<vector<int64_t>> dp(n + 1, vector<int64_t>(2, INF));
dp[s][0] = du[s];
dp[s][1] = dv[s];
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
d[s] = 0;
pq.emplace(0, s);
while (!pq.empty()) {
int64_t cost;
int from;
tie(cost, from) = pq.top();
pq.pop();
if (cost != d[from]) {
continue;
}
for (auto it : g[from]) {
int to, w;
tie(to, w) = it;
if (d[to] > d[from] + w) {
dp[to][0] = min(dp[from][0], du[to]);
dp[to][1] = min(dp[from][1], dv[to]);
d[to] = d[from] + w;
pq.emplace(d[to], to);
} else if (d[to] == d[from] + w) {
if (dp[to][0] + dp[to][1] > min(dp[from][0], du[to]) + min(dp[from][1], dv[to])) {
dp[to][0] = min(dp[from][0], du[to]);
dp[to][1] = min(dp[from][1], dv[to]);
}
}
}
}
minSelf(ans, dp[t][0] + dp[t][1]);
}
void testCase() {
int m, s, t, u, v;
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);
}
Dijkstra(u, du);
Dijkstra(v, dv);
ans = du[v]; /// poate drumul optim de la u la v este cel direct dintre ele fara commuter pass
solve(s, t); /// u - x - y - v
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
19276 KB |
Output is correct |
2 |
Correct |
220 ms |
18160 KB |
Output is correct |
3 |
Correct |
234 ms |
17812 KB |
Output is correct |
4 |
Correct |
208 ms |
18088 KB |
Output is correct |
5 |
Correct |
230 ms |
17980 KB |
Output is correct |
6 |
Correct |
216 ms |
19344 KB |
Output is correct |
7 |
Correct |
235 ms |
18292 KB |
Output is correct |
8 |
Correct |
214 ms |
18128 KB |
Output is correct |
9 |
Correct |
212 ms |
17972 KB |
Output is correct |
10 |
Correct |
195 ms |
17848 KB |
Output is correct |
11 |
Correct |
86 ms |
13608 KB |
Output is correct |
12 |
Correct |
248 ms |
17940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
18304 KB |
Output is correct |
2 |
Correct |
238 ms |
18064 KB |
Output is correct |
3 |
Correct |
226 ms |
18056 KB |
Output is correct |
4 |
Correct |
223 ms |
18076 KB |
Output is correct |
5 |
Correct |
237 ms |
18028 KB |
Output is correct |
6 |
Correct |
209 ms |
17780 KB |
Output is correct |
7 |
Correct |
252 ms |
18092 KB |
Output is correct |
8 |
Correct |
229 ms |
17992 KB |
Output is correct |
9 |
Correct |
253 ms |
18032 KB |
Output is correct |
10 |
Correct |
237 ms |
18228 KB |
Output is correct |
11 |
Correct |
98 ms |
13512 KB |
Output is correct |
12 |
Correct |
251 ms |
17828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
3404 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
13 ms |
4048 KB |
Output is correct |
5 |
Correct |
7 ms |
3388 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2764 KB |
Output is correct |
8 |
Correct |
2 ms |
2764 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
7 ms |
3276 KB |
Output is correct |
11 |
Correct |
1 ms |
2636 KB |
Output is correct |
12 |
Correct |
1 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
19276 KB |
Output is correct |
2 |
Correct |
220 ms |
18160 KB |
Output is correct |
3 |
Correct |
234 ms |
17812 KB |
Output is correct |
4 |
Correct |
208 ms |
18088 KB |
Output is correct |
5 |
Correct |
230 ms |
17980 KB |
Output is correct |
6 |
Correct |
216 ms |
19344 KB |
Output is correct |
7 |
Correct |
235 ms |
18292 KB |
Output is correct |
8 |
Correct |
214 ms |
18128 KB |
Output is correct |
9 |
Correct |
212 ms |
17972 KB |
Output is correct |
10 |
Correct |
195 ms |
17848 KB |
Output is correct |
11 |
Correct |
86 ms |
13608 KB |
Output is correct |
12 |
Correct |
248 ms |
17940 KB |
Output is correct |
13 |
Correct |
222 ms |
18304 KB |
Output is correct |
14 |
Correct |
238 ms |
18064 KB |
Output is correct |
15 |
Correct |
226 ms |
18056 KB |
Output is correct |
16 |
Correct |
223 ms |
18076 KB |
Output is correct |
17 |
Correct |
237 ms |
18028 KB |
Output is correct |
18 |
Correct |
209 ms |
17780 KB |
Output is correct |
19 |
Correct |
252 ms |
18092 KB |
Output is correct |
20 |
Correct |
229 ms |
17992 KB |
Output is correct |
21 |
Correct |
253 ms |
18032 KB |
Output is correct |
22 |
Correct |
237 ms |
18228 KB |
Output is correct |
23 |
Correct |
98 ms |
13512 KB |
Output is correct |
24 |
Correct |
251 ms |
17828 KB |
Output is correct |
25 |
Correct |
8 ms |
3404 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
2 ms |
2636 KB |
Output is correct |
28 |
Correct |
13 ms |
4048 KB |
Output is correct |
29 |
Correct |
7 ms |
3388 KB |
Output is correct |
30 |
Correct |
2 ms |
2636 KB |
Output is correct |
31 |
Correct |
2 ms |
2764 KB |
Output is correct |
32 |
Correct |
2 ms |
2764 KB |
Output is correct |
33 |
Correct |
2 ms |
2636 KB |
Output is correct |
34 |
Correct |
7 ms |
3276 KB |
Output is correct |
35 |
Correct |
1 ms |
2636 KB |
Output is correct |
36 |
Correct |
1 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
2 ms |
2636 KB |
Output is correct |
39 |
Correct |
2 ms |
2636 KB |
Output is correct |
40 |
Correct |
216 ms |
19460 KB |
Output is correct |
41 |
Correct |
211 ms |
18032 KB |
Output is correct |
42 |
Correct |
234 ms |
18064 KB |
Output is correct |
43 |
Correct |
97 ms |
13500 KB |
Output is correct |
44 |
Correct |
83 ms |
13608 KB |
Output is correct |
45 |
Correct |
198 ms |
17684 KB |
Output is correct |
46 |
Correct |
202 ms |
17704 KB |
Output is correct |
47 |
Correct |
220 ms |
17960 KB |
Output is correct |
48 |
Correct |
87 ms |
13616 KB |
Output is correct |
49 |
Correct |
185 ms |
19392 KB |
Output is correct |
50 |
Correct |
198 ms |
17648 KB |
Output is correct |
51 |
Correct |
189 ms |
17684 KB |
Output is correct |