#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long) 1e18;
template<typename T>
struct edge {
int from, to;
T cost;
};
void dijkstra(const vector< vector< edge<long long> > >& g, int s, vector<long long>& dist) {
dist.assign((int) g.size(), INF);
dist[s] = 0;
priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > pq;
pq.push({0, s});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d < dist[u]) {
continue;
}
for (auto& v : g[u]) {
if (d + v.cost < dist[v.to]) {
dist[v.to] = d + v.cost;
pq.push({dist[v.to], v.to});
}
}
}
}
void calc_dp(const vector< vector< edge<long long> > >& g, const vector<long long>& dist, const vector<long long>& dist2, int s, vector<long long>& dp) {
queue<int> que;
que.push(s);
dp.assign((int) g.size(), INF);
dp[s] = dist[s];
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto& v : g[u]) {
if (dist2[u] + v.cost == dist2[v.to] && dp[v.to] > dp[u]) {
que.push(v.to);
dp[v.to] = min(dp[u], dist[v.to]);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
vector< vector< edge<long long> > > g(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
long long c;
cin >> a >> b >> c;
g[a].push_back({a, b, c});
g[b].push_back({b, a, c});
}
vector<long long> dist_u, dist_v, dist_s, dist_t, dp1, dp2;
dijkstra(g, u, dist_u);
dijkstra(g, v, dist_v);
dijkstra(g, s, dist_s);
dijkstra(g, t, dist_t);
calc_dp(g, dist_v, dist_s, s, dp1);
calc_dp(g, dist_v, dist_t, t, dp2);
long long ans = INF;
for (int i = 1; i <= n; i++) {
if (dist_s[i] + dist_t[i] == dist_s[t]) {
ans = min(ans, dist_u[i] + min(dp1[i], dp2[i]));
}
}
cout << min(ans, dist_u[v]) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
19436 KB |
Output is correct |
2 |
Correct |
695 ms |
18248 KB |
Output is correct |
3 |
Correct |
530 ms |
19324 KB |
Output is correct |
4 |
Correct |
475 ms |
18156 KB |
Output is correct |
5 |
Correct |
510 ms |
18000 KB |
Output is correct |
6 |
Correct |
552 ms |
19652 KB |
Output is correct |
7 |
Correct |
812 ms |
18020 KB |
Output is correct |
8 |
Correct |
720 ms |
18304 KB |
Output is correct |
9 |
Correct |
488 ms |
18036 KB |
Output is correct |
10 |
Correct |
453 ms |
18184 KB |
Output is correct |
11 |
Correct |
312 ms |
12704 KB |
Output is correct |
12 |
Correct |
589 ms |
18224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
572 ms |
18272 KB |
Output is correct |
2 |
Correct |
607 ms |
18276 KB |
Output is correct |
3 |
Correct |
652 ms |
18272 KB |
Output is correct |
4 |
Correct |
615 ms |
18336 KB |
Output is correct |
5 |
Correct |
589 ms |
18136 KB |
Output is correct |
6 |
Correct |
551 ms |
18192 KB |
Output is correct |
7 |
Correct |
695 ms |
18180 KB |
Output is correct |
8 |
Correct |
596 ms |
18512 KB |
Output is correct |
9 |
Correct |
584 ms |
18132 KB |
Output is correct |
10 |
Correct |
619 ms |
18164 KB |
Output is correct |
11 |
Correct |
269 ms |
12728 KB |
Output is correct |
12 |
Correct |
550 ms |
18404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1792 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
21 ms |
2944 KB |
Output is correct |
5 |
Correct |
11 ms |
1664 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
4 ms |
512 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
18 ms |
1664 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
19436 KB |
Output is correct |
2 |
Correct |
695 ms |
18248 KB |
Output is correct |
3 |
Correct |
530 ms |
19324 KB |
Output is correct |
4 |
Correct |
475 ms |
18156 KB |
Output is correct |
5 |
Correct |
510 ms |
18000 KB |
Output is correct |
6 |
Correct |
552 ms |
19652 KB |
Output is correct |
7 |
Correct |
812 ms |
18020 KB |
Output is correct |
8 |
Correct |
720 ms |
18304 KB |
Output is correct |
9 |
Correct |
488 ms |
18036 KB |
Output is correct |
10 |
Correct |
453 ms |
18184 KB |
Output is correct |
11 |
Correct |
312 ms |
12704 KB |
Output is correct |
12 |
Correct |
589 ms |
18224 KB |
Output is correct |
13 |
Correct |
572 ms |
18272 KB |
Output is correct |
14 |
Correct |
607 ms |
18276 KB |
Output is correct |
15 |
Correct |
652 ms |
18272 KB |
Output is correct |
16 |
Correct |
615 ms |
18336 KB |
Output is correct |
17 |
Correct |
589 ms |
18136 KB |
Output is correct |
18 |
Correct |
551 ms |
18192 KB |
Output is correct |
19 |
Correct |
695 ms |
18180 KB |
Output is correct |
20 |
Correct |
596 ms |
18512 KB |
Output is correct |
21 |
Correct |
584 ms |
18132 KB |
Output is correct |
22 |
Correct |
619 ms |
18164 KB |
Output is correct |
23 |
Correct |
269 ms |
12728 KB |
Output is correct |
24 |
Correct |
550 ms |
18404 KB |
Output is correct |
25 |
Correct |
12 ms |
1792 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
21 ms |
2944 KB |
Output is correct |
29 |
Correct |
11 ms |
1664 KB |
Output is correct |
30 |
Correct |
3 ms |
512 KB |
Output is correct |
31 |
Correct |
4 ms |
512 KB |
Output is correct |
32 |
Correct |
4 ms |
512 KB |
Output is correct |
33 |
Correct |
3 ms |
512 KB |
Output is correct |
34 |
Correct |
18 ms |
1664 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
3 ms |
384 KB |
Output is correct |
38 |
Correct |
3 ms |
384 KB |
Output is correct |
39 |
Correct |
3 ms |
384 KB |
Output is correct |
40 |
Correct |
592 ms |
18960 KB |
Output is correct |
41 |
Correct |
636 ms |
18216 KB |
Output is correct |
42 |
Correct |
543 ms |
18340 KB |
Output is correct |
43 |
Correct |
269 ms |
12664 KB |
Output is correct |
44 |
Correct |
242 ms |
12664 KB |
Output is correct |
45 |
Correct |
552 ms |
17924 KB |
Output is correct |
46 |
Correct |
531 ms |
18008 KB |
Output is correct |
47 |
Correct |
503 ms |
19412 KB |
Output is correct |
48 |
Correct |
275 ms |
12792 KB |
Output is correct |
49 |
Correct |
432 ms |
19064 KB |
Output is correct |
50 |
Correct |
696 ms |
18000 KB |
Output is correct |
51 |
Correct |
491 ms |
18072 KB |
Output is correct |