#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
vector<vector<ll>> edges[100001];
unordered_set<ll> newedges[100001];
ll sdists[100001];
ll udists[100001];
ll vdists[100001];
ll visited[100001];
ll dp[2][100001];
vector<ll> topsort;
void dfs(ll a){
for (auto&i : edges[a]){
if (newedges[i[0]].count(a)) continue;
if (sdists[i[0]] == sdists[a] - i[1]){
newedges[i[0]].insert(a);
dfs(i[0]);
}
}
}
void dfs2(ll a){
for (auto&i : newedges[a]){
if (!visited[i]){
visited[i] = true;
dfs2(i);
}
}
topsort.push_back(a);
}
int main(){
ll n,m,s,t,u,v;
cin >> n >> m >> s >> t >> u >> v;
FOR(i,0,100001){
sdists[i] = LLONG_MAX / 2;
udists[i] = LLONG_MAX / 2;
vdists[i] = LLONG_MAX / 2;
}
FOR(i,0,m){
ll a,b,c;
cin >> a >> b >> c;
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;
FOR(i,0,100001) visited[i] = false;
visited[s] = true;
sdists[s] = 0;
pq.push({0,s});
while (pq.size()){
vector<ll> node = pq.top();
pq.pop();
if (node[0] != sdists[node[1]]) continue;
for (auto&i : edges[node[1]]){
if (sdists[i[0]] > sdists[node[1]] + i[1]){
sdists[i[0]] = sdists[node[1]] + i[1];
pq.push({sdists[i[0]],i[0]});
}
}
}
FOR(i,0,100001) visited[i] = false;
visited[t] = true;
dfs(t);
FOR(i,0,100001) visited[i] = false;
visited[u] = true;
udists[u] = 0;
pq.push({0,u});
while (pq.size()){
vector<ll> node = pq.top();
pq.pop();
if (node[0] != udists[node[1]]) continue;
for (auto&i : edges[node[1]]){
if (udists[i[0]] > udists[node[1]] + i[1]){
udists[i[0]] = udists[node[1]] + i[1];
pq.push({udists[i[0]],i[0]});
}
}
}
FOR(i,0,100001) visited[i] = false;
visited[v] = true;
vdists[v] = 0;
pq.push({0,v});
while (pq.size()){
vector<ll> node = pq.top();
pq.pop();
if (node[0] != vdists[node[1]]) continue;
for (auto&i : edges[node[1]]){
if (vdists[i[0]] > vdists[node[1]] + i[1]){
vdists[i[0]] = vdists[node[1]] + i[1];
pq.push({vdists[i[0]],i[0]});
}
}
}
FOR(i,0,100001) visited[i] = false;
FOR(i,1,n+1){
if (!visited[i] && newedges[i].size()){
visited[i] = true;
dfs2(i);
}
}
FOR(i,0,100001){
dp[0][i] = udists[i];
dp[1][i] = vdists[i];
}
reverse(topsort.begin(), topsort.end());
ll ans = LLONG_MAX / 2;
for (auto&i : topsort){
//cout << i << " " << dp[1][i] << " " << dp[0][i] << endl;
ans = min(ans, dp[1][i] + dp[0][i]);
for (auto&j : newedges[i]){
dp[1][j] = min(dp[1][j], dp[1][i]);
ans = min(ans, dp[1][j] + dp[0][j]);
}
}
FOR(i,0,100001){
dp[0][i] = udists[i];
dp[1][i] = vdists[i];
}
for (auto&i : topsort){
//cout << i << " " << dp[1][i] << " " << dp[0][i] << endl;
ans = min(ans, dp[1][i] + dp[0][i]);
for (auto&j : newedges[i]){
dp[0][j] = min(dp[0][j], dp[0][i]);
ans = min(ans, dp[1][j] + dp[0][j]);
}
}
ans = min(ans, vdists[u]);
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
672 ms |
46428 KB |
Output is correct |
2 |
Correct |
627 ms |
50104 KB |
Output is correct |
3 |
Correct |
726 ms |
62464 KB |
Output is correct |
4 |
Correct |
664 ms |
46432 KB |
Output is correct |
5 |
Correct |
665 ms |
53500 KB |
Output is correct |
6 |
Correct |
681 ms |
46920 KB |
Output is correct |
7 |
Correct |
686 ms |
54660 KB |
Output is correct |
8 |
Correct |
688 ms |
53648 KB |
Output is correct |
9 |
Correct |
672 ms |
45772 KB |
Output is correct |
10 |
Correct |
580 ms |
45360 KB |
Output is correct |
11 |
Correct |
288 ms |
38208 KB |
Output is correct |
12 |
Correct |
657 ms |
45840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
710 ms |
52944 KB |
Output is correct |
2 |
Correct |
651 ms |
53276 KB |
Output is correct |
3 |
Correct |
663 ms |
51876 KB |
Output is correct |
4 |
Correct |
720 ms |
52896 KB |
Output is correct |
5 |
Correct |
729 ms |
54928 KB |
Output is correct |
6 |
Correct |
694 ms |
60664 KB |
Output is correct |
7 |
Correct |
800 ms |
63072 KB |
Output is correct |
8 |
Correct |
702 ms |
53248 KB |
Output is correct |
9 |
Correct |
726 ms |
54764 KB |
Output is correct |
10 |
Correct |
714 ms |
52116 KB |
Output is correct |
11 |
Correct |
355 ms |
43680 KB |
Output is correct |
12 |
Correct |
717 ms |
61568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
16844 KB |
Output is correct |
2 |
Correct |
8 ms |
12880 KB |
Output is correct |
3 |
Correct |
8 ms |
12884 KB |
Output is correct |
4 |
Correct |
53 ms |
19996 KB |
Output is correct |
5 |
Correct |
32 ms |
16420 KB |
Output is correct |
6 |
Correct |
10 ms |
13012 KB |
Output is correct |
7 |
Correct |
11 ms |
13192 KB |
Output is correct |
8 |
Correct |
11 ms |
13384 KB |
Output is correct |
9 |
Correct |
11 ms |
13012 KB |
Output is correct |
10 |
Correct |
34 ms |
16404 KB |
Output is correct |
11 |
Correct |
8 ms |
12884 KB |
Output is correct |
12 |
Correct |
8 ms |
12884 KB |
Output is correct |
13 |
Correct |
8 ms |
12884 KB |
Output is correct |
14 |
Correct |
9 ms |
12880 KB |
Output is correct |
15 |
Correct |
9 ms |
12884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
672 ms |
46428 KB |
Output is correct |
2 |
Correct |
627 ms |
50104 KB |
Output is correct |
3 |
Correct |
726 ms |
62464 KB |
Output is correct |
4 |
Correct |
664 ms |
46432 KB |
Output is correct |
5 |
Correct |
665 ms |
53500 KB |
Output is correct |
6 |
Correct |
681 ms |
46920 KB |
Output is correct |
7 |
Correct |
686 ms |
54660 KB |
Output is correct |
8 |
Correct |
688 ms |
53648 KB |
Output is correct |
9 |
Correct |
672 ms |
45772 KB |
Output is correct |
10 |
Correct |
580 ms |
45360 KB |
Output is correct |
11 |
Correct |
288 ms |
38208 KB |
Output is correct |
12 |
Correct |
657 ms |
45840 KB |
Output is correct |
13 |
Correct |
710 ms |
52944 KB |
Output is correct |
14 |
Correct |
651 ms |
53276 KB |
Output is correct |
15 |
Correct |
663 ms |
51876 KB |
Output is correct |
16 |
Correct |
720 ms |
52896 KB |
Output is correct |
17 |
Correct |
729 ms |
54928 KB |
Output is correct |
18 |
Correct |
694 ms |
60664 KB |
Output is correct |
19 |
Correct |
800 ms |
63072 KB |
Output is correct |
20 |
Correct |
702 ms |
53248 KB |
Output is correct |
21 |
Correct |
726 ms |
54764 KB |
Output is correct |
22 |
Correct |
714 ms |
52116 KB |
Output is correct |
23 |
Correct |
355 ms |
43680 KB |
Output is correct |
24 |
Correct |
717 ms |
61568 KB |
Output is correct |
25 |
Correct |
74 ms |
16844 KB |
Output is correct |
26 |
Correct |
8 ms |
12880 KB |
Output is correct |
27 |
Correct |
8 ms |
12884 KB |
Output is correct |
28 |
Correct |
53 ms |
19996 KB |
Output is correct |
29 |
Correct |
32 ms |
16420 KB |
Output is correct |
30 |
Correct |
10 ms |
13012 KB |
Output is correct |
31 |
Correct |
11 ms |
13192 KB |
Output is correct |
32 |
Correct |
11 ms |
13384 KB |
Output is correct |
33 |
Correct |
11 ms |
13012 KB |
Output is correct |
34 |
Correct |
34 ms |
16404 KB |
Output is correct |
35 |
Correct |
8 ms |
12884 KB |
Output is correct |
36 |
Correct |
8 ms |
12884 KB |
Output is correct |
37 |
Correct |
8 ms |
12884 KB |
Output is correct |
38 |
Correct |
9 ms |
12880 KB |
Output is correct |
39 |
Correct |
9 ms |
12884 KB |
Output is correct |
40 |
Correct |
650 ms |
47856 KB |
Output is correct |
41 |
Correct |
656 ms |
46064 KB |
Output is correct |
42 |
Correct |
693 ms |
45980 KB |
Output is correct |
43 |
Correct |
382 ms |
48104 KB |
Output is correct |
44 |
Correct |
349 ms |
47828 KB |
Output is correct |
45 |
Correct |
762 ms |
62628 KB |
Output is correct |
46 |
Correct |
793 ms |
62472 KB |
Output is correct |
47 |
Correct |
625 ms |
46192 KB |
Output is correct |
48 |
Correct |
369 ms |
43944 KB |
Output is correct |
49 |
Correct |
597 ms |
47516 KB |
Output is correct |
50 |
Correct |
778 ms |
59288 KB |
Output is correct |
51 |
Correct |
772 ms |
62680 KB |
Output is correct |