#include <bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<(int)(e);i++)
#define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define CLR(s) memset(s,0,sizeof(s))
#define PB push_back
#define ITER(v) __typeof((v).begin())
#define FOREACH(i,v) for(ITER(v) i=(v).begin();i!=(v).end();i++)
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;
typedef map<int,int> mii;
typedef vector<int> vi;
const LL INF = 1LL << 60;
using Graph = vector<vector<pii>>;
using Dist = vector<LL>;
using Node = tuple<LL, int>; // <cost, node_id>
int N, M, S, T, U, V;
Graph G;
Dist compute_shortest_path(Graph &G, vector<int> src_nodes, int N) {
Dist D(N + 1, INF);
priority_queue<Node, vector<Node>, greater<Node>> pq;
for (auto &src : src_nodes) {
D[src] = 0LL;
pq.push({D[src], src});
}
while (!pq.empty()) {
LL cur;
int x;
tie(cur, x) = pq.top();
pq.pop();
if (D[x] > cur) continue;
for (auto &it : G[x]) {
LL cost;
int y;
tie(y, cost) = it;
if (cur + cost < D[y]) {
D[y] = cur + cost;
pq.push({D[y], y});
}
}
}
return D;
}
Dist S_dist, T_dist, U_dist, V_dist;
LL ST_shortest_path_cost;
Graph G_ST; // edges consisting of edges used in any shortest paths
LL dfs(Graph &G, int x, LL u_min_dist, LL v_min_dist) {
// x : current node
// DFS - traverse all possible shortest paths
LL ans = INF;
// u -> some nodes visited -> x -> v
u_min_dist = min(u_min_dist, U_dist[x]);
ans = min(ans, u_min_dist + V_dist[x]);
// v -> some nodes visited -> x -> u
v_min_dist = min(v_min_dist, V_dist[x]);
ans = min(ans, v_min_dist + U_dist[x]);
for (auto &edge : G[x]) {
int y = edge.first;
// S -> x -> y -> T is a possible S-T shortest path
//cout << x << "->" << y << endl;
ans = min(ans, dfs(G, y, u_min_dist, v_min_dist));
}
return ans;
}
void dfs_2(int x, Dist &u_min_dist, Dist &U_dist) {
// Already tried
if (u_min_dist[x] != INF) return;
// DFS - traverse all possible shortest paths
// x : current node
// V ~~> some node visited before -> x ~~> U
u_min_dist[x] = U_dist[x];
for (auto &edge : G_ST[x]) {
// S -> x -> y -> T is a possible S-T shortest path
//cout << x << "->" << y << endl;
int y = edge.first;
dfs_2(y, u_min_dist, U_dist);
u_min_dist[x] = min(u_min_dist[x], u_min_dist[y]);
}
}
LL solve() {
Dist u_min_dist(N + 1, INF);
Dist v_min_dist(N + 1, INF);
dfs_2(S, u_min_dist, U_dist);
dfs_2(S, v_min_dist, V_dist);
LL ans = INF;
FOE(x, 1, N) {
ans = min(ans, u_min_dist[x] + V_dist[x]);
ans = min(ans, v_min_dist[x] + U_dist[x]);
}
return ans;
}
int main() {
int A, B, C;
cin >> N >> M >> S >> T >> U >> V;
G.resize(N + 1);
FOR(_, 0, M) {
cin >> A >> B >> C;
G[A].PB({B, C});
G[B].PB({A, C});
}
S_dist = compute_shortest_path(G, {S}, N);
T_dist = compute_shortest_path(G, {T}, N);
U_dist = compute_shortest_path(G, {U}, N);
V_dist = compute_shortest_path(G, {V}, N);
//cout << src_dist[T] << " " << dst_dist[S] << endl;
ST_shortest_path_cost = S_dist[T];
assert (S_dist[T] == T_dist[S]);
// Case 1: Travel U -> some nodes along a shortest path -> V
G_ST.resize(N + 1);
FOE(x, 1, N) {
for (auto &edge : G[x]) {
int y, cost;
tie(y, cost) = edge;
if (S_dist[x] + cost + T_dist[y] == ST_shortest_path_cost) {
G_ST[x].PB(edge);
}
}
}
LL ans = solve();
//cout << ans << endl;
// Case 2: Travel U -> V via direct shortest path
ans = min(ans, U_dist[V]);
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
669 ms |
16116 KB |
Output is correct |
2 |
Correct |
684 ms |
16604 KB |
Output is correct |
3 |
Correct |
722 ms |
21668 KB |
Output is correct |
4 |
Correct |
654 ms |
15908 KB |
Output is correct |
5 |
Correct |
655 ms |
17172 KB |
Output is correct |
6 |
Correct |
688 ms |
16124 KB |
Output is correct |
7 |
Correct |
667 ms |
17672 KB |
Output is correct |
8 |
Correct |
655 ms |
17404 KB |
Output is correct |
9 |
Correct |
701 ms |
16144 KB |
Output is correct |
10 |
Correct |
622 ms |
15948 KB |
Output is correct |
11 |
Correct |
294 ms |
16816 KB |
Output is correct |
12 |
Correct |
697 ms |
16072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
679 ms |
18120 KB |
Output is correct |
2 |
Correct |
689 ms |
18692 KB |
Output is correct |
3 |
Correct |
713 ms |
18116 KB |
Output is correct |
4 |
Correct |
709 ms |
18400 KB |
Output is correct |
5 |
Correct |
713 ms |
19068 KB |
Output is correct |
6 |
Correct |
695 ms |
21164 KB |
Output is correct |
7 |
Correct |
744 ms |
21768 KB |
Output is correct |
8 |
Correct |
739 ms |
18520 KB |
Output is correct |
9 |
Correct |
732 ms |
19116 KB |
Output is correct |
10 |
Correct |
753 ms |
18188 KB |
Output is correct |
11 |
Correct |
332 ms |
18756 KB |
Output is correct |
12 |
Correct |
736 ms |
21452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
70 ms |
1672 KB |
Output is correct |
5 |
Correct |
36 ms |
1016 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
8 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
35 ms |
1016 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
4 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
669 ms |
16116 KB |
Output is correct |
2 |
Correct |
684 ms |
16604 KB |
Output is correct |
3 |
Correct |
722 ms |
21668 KB |
Output is correct |
4 |
Correct |
654 ms |
15908 KB |
Output is correct |
5 |
Correct |
655 ms |
17172 KB |
Output is correct |
6 |
Correct |
688 ms |
16124 KB |
Output is correct |
7 |
Correct |
667 ms |
17672 KB |
Output is correct |
8 |
Correct |
655 ms |
17404 KB |
Output is correct |
9 |
Correct |
701 ms |
16144 KB |
Output is correct |
10 |
Correct |
622 ms |
15948 KB |
Output is correct |
11 |
Correct |
294 ms |
16816 KB |
Output is correct |
12 |
Correct |
697 ms |
16072 KB |
Output is correct |
13 |
Correct |
679 ms |
18120 KB |
Output is correct |
14 |
Correct |
689 ms |
18692 KB |
Output is correct |
15 |
Correct |
713 ms |
18116 KB |
Output is correct |
16 |
Correct |
709 ms |
18400 KB |
Output is correct |
17 |
Correct |
713 ms |
19068 KB |
Output is correct |
18 |
Correct |
695 ms |
21164 KB |
Output is correct |
19 |
Correct |
744 ms |
21768 KB |
Output is correct |
20 |
Correct |
739 ms |
18520 KB |
Output is correct |
21 |
Correct |
732 ms |
19116 KB |
Output is correct |
22 |
Correct |
753 ms |
18188 KB |
Output is correct |
23 |
Correct |
332 ms |
18756 KB |
Output is correct |
24 |
Correct |
736 ms |
21452 KB |
Output is correct |
25 |
Correct |
38 ms |
1016 KB |
Output is correct |
26 |
Correct |
3 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
70 ms |
1672 KB |
Output is correct |
29 |
Correct |
36 ms |
1016 KB |
Output is correct |
30 |
Correct |
4 ms |
376 KB |
Output is correct |
31 |
Correct |
6 ms |
376 KB |
Output is correct |
32 |
Correct |
8 ms |
504 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
35 ms |
1016 KB |
Output is correct |
35 |
Correct |
3 ms |
376 KB |
Output is correct |
36 |
Correct |
3 ms |
376 KB |
Output is correct |
37 |
Correct |
3 ms |
376 KB |
Output is correct |
38 |
Correct |
4 ms |
376 KB |
Output is correct |
39 |
Correct |
4 ms |
376 KB |
Output is correct |
40 |
Correct |
692 ms |
15620 KB |
Output is correct |
41 |
Correct |
720 ms |
16008 KB |
Output is correct |
42 |
Correct |
699 ms |
16148 KB |
Output is correct |
43 |
Correct |
347 ms |
19192 KB |
Output is correct |
44 |
Correct |
343 ms |
19228 KB |
Output is correct |
45 |
Correct |
719 ms |
19252 KB |
Output is correct |
46 |
Correct |
676 ms |
19448 KB |
Output is correct |
47 |
Correct |
659 ms |
16068 KB |
Output is correct |
48 |
Correct |
345 ms |
17144 KB |
Output is correct |
49 |
Correct |
594 ms |
15596 KB |
Output is correct |
50 |
Correct |
666 ms |
18432 KB |
Output is correct |
51 |
Correct |
635 ms |
19396 KB |
Output is correct |