#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pl = pair<ll, ll>;
const int maxN = 100'000;
const ll INF = 1'000'000'000'000'000'000LL;
int N, M;
int S, T, U, V;
vector<pl> edge[1+maxN];
vll dijkstra(int src)
{
vll dist(1+N, INF);
dist[src] = 0;
set<pl> tbv;
for(int i = 1; i <= N; i++) tbv.insert({dist[i], i});
while(!tbv.empty())
{
int u = tbv.begin()->second;
tbv.erase(tbv.begin());
for(pl e: edge[u])
{
int v = e.first;
ll w = e.second;
if(dist[v] <= dist[u] + w) continue;
tbv.erase({dist[v], v});
dist[v] = dist[u] + w;
tbv.insert({dist[v], v});
}
}
return dist;
}
vll dist[1+maxN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
cin >> S >> T;
cin >> U >> V;
for(int j = 1; j <= M; j++)
{
int a, b, c;
cin >> a >> b >> c;
edge[a].push_back({b, c});
edge[b].push_back({a, c});
}
// vll dist
for(int src: {U, V, S, T}) dist[src] = dijkstra(src);
vi spv;
for(int i = 1; i <= N; i++)
if(dist[S][i] + dist[T][i] == dist[S][T])
spv.push_back(i);
sort(spv.begin(), spv.end(), [] (int u, int v)
{
return dist[S][u] < dist[S][v];
});
ll ans = dist[U][V];
vll dpU(1+N, INF), dpV(1+N, INF);
for(int u: spv)
{
dpU[u] = dist[U][u];
dpV[u] = dist[V][u];
for(pl e: edge[u])
{
int v = e.first;
ll w = e.second;
if(dist[S][v] + w + dist[T][u] != dist[S][T]) continue;
dpU[u] = min(dpU[u], dpU[v]);
dpV[u] = min(dpV[u], dpV[v]);
}
ans = min(ans, dpU[u] + dist[V][u]);
ans = min(ans, dpV[u] + dist[U][u]);
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
726 ms |
23608 KB |
Output is correct |
2 |
Correct |
630 ms |
23752 KB |
Output is correct |
3 |
Correct |
629 ms |
23648 KB |
Output is correct |
4 |
Correct |
639 ms |
23704 KB |
Output is correct |
5 |
Correct |
630 ms |
23624 KB |
Output is correct |
6 |
Correct |
794 ms |
23716 KB |
Output is correct |
7 |
Correct |
651 ms |
23636 KB |
Output is correct |
8 |
Correct |
669 ms |
23640 KB |
Output is correct |
9 |
Correct |
680 ms |
23624 KB |
Output is correct |
10 |
Correct |
604 ms |
23700 KB |
Output is correct |
11 |
Correct |
396 ms |
18792 KB |
Output is correct |
12 |
Correct |
675 ms |
23628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
727 ms |
24440 KB |
Output is correct |
2 |
Correct |
699 ms |
24528 KB |
Output is correct |
3 |
Correct |
683 ms |
24392 KB |
Output is correct |
4 |
Correct |
785 ms |
27844 KB |
Output is correct |
5 |
Correct |
759 ms |
27884 KB |
Output is correct |
6 |
Correct |
735 ms |
28148 KB |
Output is correct |
7 |
Correct |
665 ms |
27876 KB |
Output is correct |
8 |
Correct |
751 ms |
27896 KB |
Output is correct |
9 |
Correct |
744 ms |
27860 KB |
Output is correct |
10 |
Correct |
742 ms |
27936 KB |
Output is correct |
11 |
Correct |
408 ms |
21768 KB |
Output is correct |
12 |
Correct |
681 ms |
28160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
6348 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
5020 KB |
Output is correct |
4 |
Correct |
16 ms |
8460 KB |
Output is correct |
5 |
Correct |
11 ms |
6716 KB |
Output is correct |
6 |
Correct |
5 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5196 KB |
Output is correct |
8 |
Correct |
5 ms |
5208 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
9 ms |
6680 KB |
Output is correct |
11 |
Correct |
3 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
5020 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
3 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
726 ms |
23608 KB |
Output is correct |
2 |
Correct |
630 ms |
23752 KB |
Output is correct |
3 |
Correct |
629 ms |
23648 KB |
Output is correct |
4 |
Correct |
639 ms |
23704 KB |
Output is correct |
5 |
Correct |
630 ms |
23624 KB |
Output is correct |
6 |
Correct |
794 ms |
23716 KB |
Output is correct |
7 |
Correct |
651 ms |
23636 KB |
Output is correct |
8 |
Correct |
669 ms |
23640 KB |
Output is correct |
9 |
Correct |
680 ms |
23624 KB |
Output is correct |
10 |
Correct |
604 ms |
23700 KB |
Output is correct |
11 |
Correct |
396 ms |
18792 KB |
Output is correct |
12 |
Correct |
675 ms |
23628 KB |
Output is correct |
13 |
Correct |
727 ms |
24440 KB |
Output is correct |
14 |
Correct |
699 ms |
24528 KB |
Output is correct |
15 |
Correct |
683 ms |
24392 KB |
Output is correct |
16 |
Correct |
785 ms |
27844 KB |
Output is correct |
17 |
Correct |
759 ms |
27884 KB |
Output is correct |
18 |
Correct |
735 ms |
28148 KB |
Output is correct |
19 |
Correct |
665 ms |
27876 KB |
Output is correct |
20 |
Correct |
751 ms |
27896 KB |
Output is correct |
21 |
Correct |
744 ms |
27860 KB |
Output is correct |
22 |
Correct |
742 ms |
27936 KB |
Output is correct |
23 |
Correct |
408 ms |
21768 KB |
Output is correct |
24 |
Correct |
681 ms |
28160 KB |
Output is correct |
25 |
Correct |
9 ms |
6348 KB |
Output is correct |
26 |
Correct |
3 ms |
4940 KB |
Output is correct |
27 |
Correct |
3 ms |
5020 KB |
Output is correct |
28 |
Correct |
16 ms |
8460 KB |
Output is correct |
29 |
Correct |
11 ms |
6716 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
4 ms |
5196 KB |
Output is correct |
32 |
Correct |
5 ms |
5208 KB |
Output is correct |
33 |
Correct |
4 ms |
5068 KB |
Output is correct |
34 |
Correct |
9 ms |
6680 KB |
Output is correct |
35 |
Correct |
3 ms |
5004 KB |
Output is correct |
36 |
Correct |
3 ms |
5020 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
39 |
Correct |
3 ms |
5068 KB |
Output is correct |
40 |
Correct |
694 ms |
27968 KB |
Output is correct |
41 |
Correct |
762 ms |
28632 KB |
Output is correct |
42 |
Correct |
702 ms |
28740 KB |
Output is correct |
43 |
Correct |
400 ms |
21712 KB |
Output is correct |
44 |
Correct |
427 ms |
21800 KB |
Output is correct |
45 |
Correct |
601 ms |
27872 KB |
Output is correct |
46 |
Correct |
604 ms |
27616 KB |
Output is correct |
47 |
Correct |
702 ms |
28144 KB |
Output is correct |
48 |
Correct |
408 ms |
21124 KB |
Output is correct |
49 |
Correct |
513 ms |
27568 KB |
Output is correct |
50 |
Correct |
626 ms |
27848 KB |
Output is correct |
51 |
Correct |
565 ms |
27760 KB |
Output is correct |