#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]) {
if (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 |
582 ms |
19584 KB |
Output is correct |
2 |
Correct |
713 ms |
18352 KB |
Output is correct |
3 |
Correct |
612 ms |
20160 KB |
Output is correct |
4 |
Correct |
529 ms |
19052 KB |
Output is correct |
5 |
Correct |
641 ms |
18712 KB |
Output is correct |
6 |
Correct |
598 ms |
20228 KB |
Output is correct |
7 |
Correct |
740 ms |
18748 KB |
Output is correct |
8 |
Correct |
725 ms |
21836 KB |
Output is correct |
9 |
Correct |
617 ms |
22544 KB |
Output is correct |
10 |
Correct |
490 ms |
22616 KB |
Output is correct |
11 |
Correct |
292 ms |
14840 KB |
Output is correct |
12 |
Correct |
595 ms |
22388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
621 ms |
18136 KB |
Output is correct |
2 |
Correct |
586 ms |
18308 KB |
Output is correct |
3 |
Correct |
590 ms |
18196 KB |
Output is correct |
4 |
Correct |
572 ms |
18276 KB |
Output is correct |
5 |
Correct |
547 ms |
18284 KB |
Output is correct |
6 |
Correct |
616 ms |
18512 KB |
Output is correct |
7 |
Correct |
715 ms |
18320 KB |
Output is correct |
8 |
Correct |
696 ms |
18148 KB |
Output is correct |
9 |
Correct |
675 ms |
18176 KB |
Output is correct |
10 |
Correct |
592 ms |
18152 KB |
Output is correct |
11 |
Correct |
273 ms |
12664 KB |
Output is correct |
12 |
Correct |
548 ms |
18456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1920 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
22 ms |
3712 KB |
Output is correct |
5 |
Correct |
13 ms |
2048 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
640 KB |
Output is correct |
9 |
Correct |
4 ms |
512 KB |
Output is correct |
10 |
Correct |
13 ms |
2048 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
424 KB |
Output is correct |
14 |
Correct |
4 ms |
512 KB |
Output is correct |
15 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
582 ms |
19584 KB |
Output is correct |
2 |
Correct |
713 ms |
18352 KB |
Output is correct |
3 |
Correct |
612 ms |
20160 KB |
Output is correct |
4 |
Correct |
529 ms |
19052 KB |
Output is correct |
5 |
Correct |
641 ms |
18712 KB |
Output is correct |
6 |
Correct |
598 ms |
20228 KB |
Output is correct |
7 |
Correct |
740 ms |
18748 KB |
Output is correct |
8 |
Correct |
725 ms |
21836 KB |
Output is correct |
9 |
Correct |
617 ms |
22544 KB |
Output is correct |
10 |
Correct |
490 ms |
22616 KB |
Output is correct |
11 |
Correct |
292 ms |
14840 KB |
Output is correct |
12 |
Correct |
595 ms |
22388 KB |
Output is correct |
13 |
Correct |
621 ms |
18136 KB |
Output is correct |
14 |
Correct |
586 ms |
18308 KB |
Output is correct |
15 |
Correct |
590 ms |
18196 KB |
Output is correct |
16 |
Correct |
572 ms |
18276 KB |
Output is correct |
17 |
Correct |
547 ms |
18284 KB |
Output is correct |
18 |
Correct |
616 ms |
18512 KB |
Output is correct |
19 |
Correct |
715 ms |
18320 KB |
Output is correct |
20 |
Correct |
696 ms |
18148 KB |
Output is correct |
21 |
Correct |
675 ms |
18176 KB |
Output is correct |
22 |
Correct |
592 ms |
18152 KB |
Output is correct |
23 |
Correct |
273 ms |
12664 KB |
Output is correct |
24 |
Correct |
548 ms |
18456 KB |
Output is correct |
25 |
Correct |
14 ms |
1920 KB |
Output is correct |
26 |
Correct |
3 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
22 ms |
3712 KB |
Output is correct |
29 |
Correct |
13 ms |
2048 KB |
Output is correct |
30 |
Correct |
3 ms |
512 KB |
Output is correct |
31 |
Correct |
5 ms |
512 KB |
Output is correct |
32 |
Correct |
5 ms |
640 KB |
Output is correct |
33 |
Correct |
4 ms |
512 KB |
Output is correct |
34 |
Correct |
13 ms |
2048 KB |
Output is correct |
35 |
Correct |
3 ms |
384 KB |
Output is correct |
36 |
Correct |
3 ms |
384 KB |
Output is correct |
37 |
Correct |
3 ms |
424 KB |
Output is correct |
38 |
Correct |
4 ms |
512 KB |
Output is correct |
39 |
Correct |
3 ms |
512 KB |
Output is correct |
40 |
Correct |
487 ms |
23264 KB |
Output is correct |
41 |
Correct |
569 ms |
22560 KB |
Output is correct |
42 |
Correct |
540 ms |
22540 KB |
Output is correct |
43 |
Correct |
229 ms |
14840 KB |
Output is correct |
44 |
Correct |
253 ms |
14784 KB |
Output is correct |
45 |
Correct |
490 ms |
21308 KB |
Output is correct |
46 |
Correct |
474 ms |
21044 KB |
Output is correct |
47 |
Correct |
448 ms |
23188 KB |
Output is correct |
48 |
Correct |
268 ms |
14200 KB |
Output is correct |
49 |
Correct |
386 ms |
22784 KB |
Output is correct |
50 |
Correct |
574 ms |
21464 KB |
Output is correct |
51 |
Correct |
440 ms |
21340 KB |
Output is correct |