#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
int s,t,u,v;
cin >> s >> t >> u >> v;
--s,--t,--u,--v;
vector<vector<pair<int,int>>> adj(n);
for (int x,y,w;m--;) {
cin >> x >> y >> w;
--x,--y;
adj[x].emplace_back(y,w);
adj[y].emplace_back(x,w);
}
const ll inf = 1e18;
auto dijkstra = [&](int source) {
vector<ll> dist(n,inf);
dist[source] = 0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
q.emplace(0,source);
while(!q.empty()) {
auto [d,x] = q.top(); q.pop();
if (dist[x] != d) { continue; }
for (auto &[y,w]: adj[x]) if (cmin(dist[y],dist[x]+w)) {
q.emplace(dist[y],y);
}
}
return dist;
};
vector<vector<int>> sp_adj(n);
auto D = dijkstra(s);
vector<bool> in_sp(n);
queue<int> q;
q.push(t);
in_sp[t] = true;
vector<int> in(n);
while(!q.empty()) {
int x = q.front(); q.pop();
for (auto &[y,w]: adj[x]) if (D[x] == D[y] + w) {
sp_adj[x].push_back(y);
// cout << "added reverse-edge " << 1+x << " " << 1+y << endl;
in[y]++;
if (!in_sp[y]) {
in_sp[y] = true;
q.push(y);
}
}
}
auto DU = dijkstra(u), DV = dijkstra(v);
vector<ll> dp(n,inf),dp2(n,inf);
assert(in[t] == 0);
q.push(t);
ll ans = DU[v];
while(!q.empty()) {
int x = q.front(); q.pop();
cmin(dp[x],DV[x]);
cmin(dp2[x],DU[x]);
cmin(ans,dp[x]+DU[x]);
cmin(ans,dp2[x]+DV[x]);
for (int &y: sp_adj[x]) {
cmin(dp[y],dp[x]);
cmin(dp2[y],dp2[x]);
if (--in[y] == 0) {
q.push(y);
}
}
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
20960 KB |
Output is correct |
2 |
Correct |
153 ms |
19872 KB |
Output is correct |
3 |
Correct |
188 ms |
21176 KB |
Output is correct |
4 |
Correct |
158 ms |
20872 KB |
Output is correct |
5 |
Correct |
189 ms |
20412 KB |
Output is correct |
6 |
Correct |
162 ms |
21000 KB |
Output is correct |
7 |
Correct |
175 ms |
20864 KB |
Output is correct |
8 |
Correct |
187 ms |
20564 KB |
Output is correct |
9 |
Correct |
148 ms |
20300 KB |
Output is correct |
10 |
Correct |
128 ms |
20036 KB |
Output is correct |
11 |
Correct |
52 ms |
15696 KB |
Output is correct |
12 |
Correct |
150 ms |
20208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
19984 KB |
Output is correct |
2 |
Correct |
170 ms |
19972 KB |
Output is correct |
3 |
Correct |
169 ms |
19784 KB |
Output is correct |
4 |
Correct |
184 ms |
19848 KB |
Output is correct |
5 |
Correct |
235 ms |
20148 KB |
Output is correct |
6 |
Correct |
168 ms |
21056 KB |
Output is correct |
7 |
Correct |
172 ms |
21072 KB |
Output is correct |
8 |
Correct |
166 ms |
19864 KB |
Output is correct |
9 |
Correct |
168 ms |
20280 KB |
Output is correct |
10 |
Correct |
182 ms |
19748 KB |
Output is correct |
11 |
Correct |
54 ms |
16476 KB |
Output is correct |
12 |
Correct |
185 ms |
21136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1372 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
9 ms |
2432 KB |
Output is correct |
5 |
Correct |
5 ms |
1372 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
1412 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
20960 KB |
Output is correct |
2 |
Correct |
153 ms |
19872 KB |
Output is correct |
3 |
Correct |
188 ms |
21176 KB |
Output is correct |
4 |
Correct |
158 ms |
20872 KB |
Output is correct |
5 |
Correct |
189 ms |
20412 KB |
Output is correct |
6 |
Correct |
162 ms |
21000 KB |
Output is correct |
7 |
Correct |
175 ms |
20864 KB |
Output is correct |
8 |
Correct |
187 ms |
20564 KB |
Output is correct |
9 |
Correct |
148 ms |
20300 KB |
Output is correct |
10 |
Correct |
128 ms |
20036 KB |
Output is correct |
11 |
Correct |
52 ms |
15696 KB |
Output is correct |
12 |
Correct |
150 ms |
20208 KB |
Output is correct |
13 |
Correct |
162 ms |
19984 KB |
Output is correct |
14 |
Correct |
170 ms |
19972 KB |
Output is correct |
15 |
Correct |
169 ms |
19784 KB |
Output is correct |
16 |
Correct |
184 ms |
19848 KB |
Output is correct |
17 |
Correct |
235 ms |
20148 KB |
Output is correct |
18 |
Correct |
168 ms |
21056 KB |
Output is correct |
19 |
Correct |
172 ms |
21072 KB |
Output is correct |
20 |
Correct |
166 ms |
19864 KB |
Output is correct |
21 |
Correct |
168 ms |
20280 KB |
Output is correct |
22 |
Correct |
182 ms |
19748 KB |
Output is correct |
23 |
Correct |
54 ms |
16476 KB |
Output is correct |
24 |
Correct |
185 ms |
21136 KB |
Output is correct |
25 |
Correct |
5 ms |
1372 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
9 ms |
2432 KB |
Output is correct |
29 |
Correct |
5 ms |
1372 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
2 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
5 ms |
1412 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
504 KB |
Output is correct |
40 |
Correct |
144 ms |
21400 KB |
Output is correct |
41 |
Correct |
142 ms |
20024 KB |
Output is correct |
42 |
Correct |
190 ms |
20124 KB |
Output is correct |
43 |
Correct |
60 ms |
17700 KB |
Output is correct |
44 |
Correct |
61 ms |
17748 KB |
Output is correct |
45 |
Correct |
166 ms |
21796 KB |
Output is correct |
46 |
Correct |
149 ms |
21548 KB |
Output is correct |
47 |
Correct |
145 ms |
20780 KB |
Output is correct |
48 |
Correct |
89 ms |
17232 KB |
Output is correct |
49 |
Correct |
123 ms |
20936 KB |
Output is correct |
50 |
Correct |
156 ms |
21172 KB |
Output is correct |
51 |
Correct |
152 ms |
21680 KB |
Output is correct |