#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int, ll>>> adj;
vector<vector<int>> nadj;
vector<vector<int>> nradj;
int n, m, s, t, u, v;
int main () {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> s >> t >> u >> v;
s--; t--; u--; v--;
adj.resize(n);
nadj.resize(n);
nradj.resize(n);
for (int i = 0; i < m; i++) {
int a, b; ll c; cin >> a >> b >> c; a--; b--;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
vector<ll> dist(n);
vector<bool> vis(n);
pq.push({0, t});
while (!pq.empty()) {
auto p = pq.top(); pq.pop();
int node = p.second;
ll len = p.first;
if (vis[node]) continue;
dist[node]=len;
vis[node]=true;
for (auto i : adj[node]) {
if (!vis[i.first]) pq.push({len+i.second, i.first});
}
}
fill(vis.begin(), vis.end(), false);
queue<int> q;
q.push(s);
while (!q.empty()) {
int node = q.front(); q.pop();
if (vis[node]) continue;
vis[node]=true;
for (auto i : adj[node]) {
if (vis[i.first]) continue;
if (dist[i.first]+i.second==dist[node]) {
nadj[node].push_back(i.first);
nradj[i.first].push_back(node);
q.push(i.first);
}
}
}
vector<ll> udist(n), vdist(n);
while (!pq.empty()) pq.pop();
fill(vis.begin(), vis.end(), false);
pq.push({0, u});
while (!pq.empty()) {
auto p = pq.top(); pq.pop();
int node = p.second;
ll len = p.first;
if (vis[node]) continue;
udist[node]=len;
vis[node]=true;
for (auto i : adj[node]) {
if (!vis[i.first]) pq.push({len+i.second, i.first});
}
}
while (!pq.empty()) pq.pop();
fill(vis.begin(), vis.end(), false);
pq.push({0, v});
while (!pq.empty()) {
auto p = pq.top(); pq.pop();
int node = p.second;
ll len = p.first;
if (vis[node]) continue;
vdist[node]=len;
vis[node]=true;
for (auto i : adj[node]) {
if (!vis[i.first]) pq.push({len+i.second, i.first});
}
}
vector<int> nchild(n);
set<int> s;
vector<ll> dp1(n);
vector<ll> dp2(n);
for (int i = 0; i < n; i++) {
nchild[i] = nadj[i].size();
if (nchild[i]==0) s.insert(i);
dp1[i]=vdist[i];
dp2[i]=udist[i];
}
ll ans = 1e18;
while (!s.empty()) {
auto node = *s.begin();
s.erase(s.begin());
for (auto child : nadj[node]) {
dp1[node] = min(dp1[node], dp1[child]);
dp2[node] = min(dp2[node], dp2[child]);
}
ans = min(ans, udist[node]+dp1[node]);
ans = min(ans, vdist[node]+dp2[node]);
for (auto parent : nradj[node]) {
if (--nchild[parent]==0) {
s.insert(parent);
}
}
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
298 ms |
31728 KB |
Output is correct |
2 |
Correct |
306 ms |
31376 KB |
Output is correct |
3 |
Correct |
321 ms |
32260 KB |
Output is correct |
4 |
Correct |
325 ms |
31372 KB |
Output is correct |
5 |
Correct |
331 ms |
31380 KB |
Output is correct |
6 |
Correct |
353 ms |
31728 KB |
Output is correct |
7 |
Correct |
352 ms |
31760 KB |
Output is correct |
8 |
Correct |
368 ms |
31780 KB |
Output is correct |
9 |
Correct |
304 ms |
31788 KB |
Output is correct |
10 |
Correct |
316 ms |
31932 KB |
Output is correct |
11 |
Correct |
122 ms |
23884 KB |
Output is correct |
12 |
Correct |
329 ms |
31728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
336 ms |
31568 KB |
Output is correct |
2 |
Correct |
329 ms |
31176 KB |
Output is correct |
3 |
Correct |
313 ms |
31096 KB |
Output is correct |
4 |
Correct |
303 ms |
31156 KB |
Output is correct |
5 |
Correct |
349 ms |
31172 KB |
Output is correct |
6 |
Correct |
301 ms |
32044 KB |
Output is correct |
7 |
Correct |
366 ms |
31676 KB |
Output is correct |
8 |
Correct |
297 ms |
31188 KB |
Output is correct |
9 |
Correct |
299 ms |
31252 KB |
Output is correct |
10 |
Correct |
353 ms |
31044 KB |
Output is correct |
11 |
Correct |
146 ms |
24268 KB |
Output is correct |
12 |
Correct |
357 ms |
32120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
2388 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
32 ms |
4316 KB |
Output is correct |
5 |
Correct |
17 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
456 KB |
Output is correct |
7 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
298 ms |
31728 KB |
Output is correct |
2 |
Correct |
306 ms |
31376 KB |
Output is correct |
3 |
Correct |
321 ms |
32260 KB |
Output is correct |
4 |
Correct |
325 ms |
31372 KB |
Output is correct |
5 |
Correct |
331 ms |
31380 KB |
Output is correct |
6 |
Correct |
353 ms |
31728 KB |
Output is correct |
7 |
Correct |
352 ms |
31760 KB |
Output is correct |
8 |
Correct |
368 ms |
31780 KB |
Output is correct |
9 |
Correct |
304 ms |
31788 KB |
Output is correct |
10 |
Correct |
316 ms |
31932 KB |
Output is correct |
11 |
Correct |
122 ms |
23884 KB |
Output is correct |
12 |
Correct |
329 ms |
31728 KB |
Output is correct |
13 |
Correct |
336 ms |
31568 KB |
Output is correct |
14 |
Correct |
329 ms |
31176 KB |
Output is correct |
15 |
Correct |
313 ms |
31096 KB |
Output is correct |
16 |
Correct |
303 ms |
31156 KB |
Output is correct |
17 |
Correct |
349 ms |
31172 KB |
Output is correct |
18 |
Correct |
301 ms |
32044 KB |
Output is correct |
19 |
Correct |
366 ms |
31676 KB |
Output is correct |
20 |
Correct |
297 ms |
31188 KB |
Output is correct |
21 |
Correct |
299 ms |
31252 KB |
Output is correct |
22 |
Correct |
353 ms |
31044 KB |
Output is correct |
23 |
Correct |
146 ms |
24268 KB |
Output is correct |
24 |
Correct |
357 ms |
32120 KB |
Output is correct |
25 |
Correct |
16 ms |
2388 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
32 ms |
4316 KB |
Output is correct |
29 |
Correct |
17 ms |
2636 KB |
Output is correct |
30 |
Correct |
2 ms |
456 KB |
Output is correct |
31 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |