#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(ll int i = 0; i < (ll int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
ll int inf = 1e18;
vector<ll int> distancesS, distancesU, distancesV, distances;
vector<vector<pair<int, ll int>>> adj;
vector<vector<int>> from;
vector<bool> vis;
void djkstra(ll int start) {
fill(all(distances), inf);
distances[start] = 0;
priority_queue<pair<ll int, ll int>> pq;
pq.emplace(0, start);
while (pq.size()) {
ll int node, d;
tie(d, node) = pq.top();
pq.pop();
d = -1 * d;
if (distances[node] != d) continue;
for (auto [v, wt] : adj[node]) {
ll int new_dist = d + wt;
if (new_dist < distances[v]) {
distances[v] = new_dist;
pq.emplace(-new_dist, v);
}
}
}
}
ll int ans = 0;
vector<ll int> mem;
ll int dfs2(ll int u) {
if (vis[u]) return mem[u];
vis[u] = 1;
ll int mn = inf;
for (ll int v : from[u]) {
mn = min(mn, dfs2(v));
}
ans = min(ans, mn + distancesV[u]);
return mem[u] = min(mn, distancesU[u]);
}
void solve() {
int n, m; cin >> n >> m;
int s, t; cin >> s >> t; s--, t--;
int U, V; cin >> U >> V; U--, V--;
adj.resize(n);
vis.resize(n);
distances.resize(n);
distancesS.resize(n);
distancesU.resize(n);
distancesV.resize(n);
from.resize(n);
mem.resize(n);
for (ll int i = 0; i < m; i++) {
ll int a, b, c; cin >> a >> b >> c;
a--, b--;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
// run djkstra
djkstra(U); for (ll int i = 0; i < n; i++) distancesU[i] = distances[i];
djkstra(V); for (ll int i = 0; i < n; i++) distancesV[i] = distances[i];
auto djkstra1 = [&]() {
// I know u and v
fill(all(distancesS), inf);
distancesS[s] = 0;
priority_queue<pair<ll int, ll int>> pq;
pq.emplace(0, s);
while (pq.size()) {
auto [dist, node] = pq.top();
pq.pop();
dist = dist * -1;
if (distancesS[node] != dist) continue;
for (auto [v, wt] : adj[node]) {
ll int new_dist = dist + wt;
if (new_dist < distancesS[v]) {
distancesS[v] = new_dist;
from[v].clear();
from[v].push_back(node);
pq.emplace(-new_dist, v);
} else if (new_dist == distancesS[v]) {
from[v].push_back(node);
}
}
}
};
djkstra1();
ans = distancesU[V];
fill(all(mem), 0);
dfs2(t);
fill(all(vis), 0);
distancesV.swap(distancesU);
fill(all(mem), inf);
dfs2(t);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
23500 KB |
Output is correct |
2 |
Correct |
269 ms |
22684 KB |
Output is correct |
3 |
Correct |
252 ms |
25496 KB |
Output is correct |
4 |
Correct |
233 ms |
22600 KB |
Output is correct |
5 |
Correct |
239 ms |
22468 KB |
Output is correct |
6 |
Correct |
240 ms |
23288 KB |
Output is correct |
7 |
Correct |
250 ms |
22760 KB |
Output is correct |
8 |
Correct |
247 ms |
22840 KB |
Output is correct |
9 |
Correct |
232 ms |
22488 KB |
Output is correct |
10 |
Correct |
207 ms |
22320 KB |
Output is correct |
11 |
Correct |
100 ms |
18936 KB |
Output is correct |
12 |
Correct |
250 ms |
22676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
23984 KB |
Output is correct |
2 |
Correct |
249 ms |
24008 KB |
Output is correct |
3 |
Correct |
247 ms |
23724 KB |
Output is correct |
4 |
Correct |
252 ms |
24020 KB |
Output is correct |
5 |
Correct |
258 ms |
24252 KB |
Output is correct |
6 |
Correct |
255 ms |
25172 KB |
Output is correct |
7 |
Correct |
263 ms |
25732 KB |
Output is correct |
8 |
Correct |
262 ms |
24064 KB |
Output is correct |
9 |
Correct |
258 ms |
24428 KB |
Output is correct |
10 |
Correct |
249 ms |
23776 KB |
Output is correct |
11 |
Correct |
114 ms |
19916 KB |
Output is correct |
12 |
Correct |
250 ms |
25288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1748 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
13 ms |
3028 KB |
Output is correct |
5 |
Correct |
6 ms |
1620 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
6 ms |
1620 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
23500 KB |
Output is correct |
2 |
Correct |
269 ms |
22684 KB |
Output is correct |
3 |
Correct |
252 ms |
25496 KB |
Output is correct |
4 |
Correct |
233 ms |
22600 KB |
Output is correct |
5 |
Correct |
239 ms |
22468 KB |
Output is correct |
6 |
Correct |
240 ms |
23288 KB |
Output is correct |
7 |
Correct |
250 ms |
22760 KB |
Output is correct |
8 |
Correct |
247 ms |
22840 KB |
Output is correct |
9 |
Correct |
232 ms |
22488 KB |
Output is correct |
10 |
Correct |
207 ms |
22320 KB |
Output is correct |
11 |
Correct |
100 ms |
18936 KB |
Output is correct |
12 |
Correct |
250 ms |
22676 KB |
Output is correct |
13 |
Correct |
248 ms |
23984 KB |
Output is correct |
14 |
Correct |
249 ms |
24008 KB |
Output is correct |
15 |
Correct |
247 ms |
23724 KB |
Output is correct |
16 |
Correct |
252 ms |
24020 KB |
Output is correct |
17 |
Correct |
258 ms |
24252 KB |
Output is correct |
18 |
Correct |
255 ms |
25172 KB |
Output is correct |
19 |
Correct |
263 ms |
25732 KB |
Output is correct |
20 |
Correct |
262 ms |
24064 KB |
Output is correct |
21 |
Correct |
258 ms |
24428 KB |
Output is correct |
22 |
Correct |
249 ms |
23776 KB |
Output is correct |
23 |
Correct |
114 ms |
19916 KB |
Output is correct |
24 |
Correct |
250 ms |
25288 KB |
Output is correct |
25 |
Correct |
7 ms |
1748 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
13 ms |
3028 KB |
Output is correct |
29 |
Correct |
6 ms |
1620 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
6 ms |
1620 KB |
Output is correct |
35 |
Correct |
0 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
218 ms |
22536 KB |
Output is correct |
41 |
Correct |
253 ms |
22604 KB |
Output is correct |
42 |
Correct |
240 ms |
22512 KB |
Output is correct |
43 |
Correct |
114 ms |
19284 KB |
Output is correct |
44 |
Correct |
111 ms |
19228 KB |
Output is correct |
45 |
Correct |
246 ms |
22444 KB |
Output is correct |
46 |
Correct |
248 ms |
22260 KB |
Output is correct |
47 |
Correct |
242 ms |
22484 KB |
Output is correct |
48 |
Correct |
107 ms |
17652 KB |
Output is correct |
49 |
Correct |
207 ms |
22676 KB |
Output is correct |
50 |
Correct |
248 ms |
22320 KB |
Output is correct |
51 |
Correct |
236 ms |
22312 KB |
Output is correct |