#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>
#define i64 int64_t
const i64 inf=1e17;
const int max_n=100000;
std::vector< std::pair<int, int> > adjList[1+max_n];
i64 dist_u[1+max_n], dist_v[1+max_n], dist_s[1+max_n];
bool visited[1+max_n];
i64 dp[2][1+max_n];
i64 result;
void dijkstra(int start, i64 dist[]) {
std::priority_queue< std::pair<i64, int> > pq;
memset(visited, false, sizeof(visited));
pq.push({0, start});
while (!pq.empty()) {
i64 cdist=pq.top().first;
int cvertex=pq.top().second;
pq.pop();
if (!visited[cvertex]) {
visited[cvertex]=true;
dist[cvertex]=-cdist;
for (auto& to: adjList[cvertex]) {
pq.push({cdist-to.second, to.first});
}
}
}
}
void dijkstra2(int start, int finish) {
std::fill(dp[0], dp[0]+1+max_n, inf);
std::fill(dp[1], dp[1]+1+max_n, inf);
memset(visited, false, sizeof(visited));
std::priority_queue< std::pair< i64, std::pair<int, int> > > pq;
pq.push({0, {start, 0}});
while (!pq.empty()) {
i64 cdist=pq.top().first;
int cvertex=pq.top().second.first;
int cpar=pq.top().second.second;
pq.pop();
if (!visited[cvertex]) {
visited[cvertex]=true;
dist_s[cvertex]=-cdist;
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
for (auto& to: adjList[cvertex]) {
pq.push({cdist-to.second, {to.first, cvertex}});
}
}
else {
if (dist_s[cvertex]==-cdist and
std::min(dist_u[cvertex], dp[0][cpar])+std::min(dist_v[cvertex], dp[1][cpar])<=dp[0][cvertex]+dp[1][cvertex]) {
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
}
}
}
/*while (!pq.empty()) {
int cdist=-pq.top().first;
int cvertex=pq.top().second.first;;
int cpar=pq.top().second.second;
pq.pop();
if (dist_s[cvertex]<cdist) continue;
for (auto& to: adjList[cvertex]) {
i64 new_dist=cdist+to.second;
if (dist_s[to.first]>new_dist) {
pq.push({-(dist_s[to.first]=new_dist), {to.first, cvertex}});
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
}
else {
if (dist_s[to.first]==new_dist and
std::min(dist_u[cvertex], dp[0][cpar])+std::min(dist_v[cvertex], dp[1][cpar])<=dp[0][cvertex]+dp[1][cvertex]) {
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
}
}
}
}*/
result=std::min(result, dp[0][finish]+dp[1][finish]);
}
int main() {
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
int n, m, s, t, u, v;
std::cin>>n>>m>>s>>t>>u>>v;
//--s, --t, --u, --v;
for (int i=0; i<m; ++i) {
int a, b, c; std::cin>>a>>b>>c;
//--a, --b;
adjList[a].push_back({b, c});
adjList[b].push_back({a, c});
}
dijkstra(u, dist_u);
dijkstra(v, dist_v);
result=dist_u[v];
/*for (int i=1; i<=n; ++i) {
std::cout<<"#"<<i<<" "<<dist_u[i]<<"\n";
}*/
dijkstra2(s, t);
dijkstra2(t, s);
std::cout<<result;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
559 ms |
19780 KB |
Output is correct |
2 |
Correct |
529 ms |
23060 KB |
Output is correct |
3 |
Correct |
515 ms |
22856 KB |
Output is correct |
4 |
Correct |
570 ms |
23036 KB |
Output is correct |
5 |
Correct |
524 ms |
20484 KB |
Output is correct |
6 |
Correct |
578 ms |
23660 KB |
Output is correct |
7 |
Correct |
511 ms |
22904 KB |
Output is correct |
8 |
Correct |
506 ms |
22916 KB |
Output is correct |
9 |
Correct |
583 ms |
24072 KB |
Output is correct |
10 |
Correct |
536 ms |
24092 KB |
Output is correct |
11 |
Correct |
164 ms |
12012 KB |
Output is correct |
12 |
Correct |
555 ms |
24280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
558 ms |
19596 KB |
Output is correct |
2 |
Correct |
478 ms |
16980 KB |
Output is correct |
3 |
Correct |
488 ms |
22856 KB |
Output is correct |
4 |
Correct |
496 ms |
20464 KB |
Output is correct |
5 |
Correct |
496 ms |
20416 KB |
Output is correct |
6 |
Correct |
516 ms |
22828 KB |
Output is correct |
7 |
Correct |
490 ms |
20464 KB |
Output is correct |
8 |
Correct |
488 ms |
20544 KB |
Output is correct |
9 |
Correct |
500 ms |
20420 KB |
Output is correct |
10 |
Correct |
502 ms |
22604 KB |
Output is correct |
11 |
Correct |
153 ms |
11884 KB |
Output is correct |
12 |
Correct |
519 ms |
22856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
6004 KB |
Output is correct |
2 |
Correct |
4 ms |
4460 KB |
Output is correct |
3 |
Correct |
4 ms |
4460 KB |
Output is correct |
4 |
Correct |
78 ms |
8320 KB |
Output is correct |
5 |
Correct |
40 ms |
7036 KB |
Output is correct |
6 |
Correct |
5 ms |
4480 KB |
Output is correct |
7 |
Correct |
6 ms |
4588 KB |
Output is correct |
8 |
Correct |
8 ms |
4588 KB |
Output is correct |
9 |
Correct |
5 ms |
4460 KB |
Output is correct |
10 |
Correct |
38 ms |
6944 KB |
Output is correct |
11 |
Correct |
3 ms |
4332 KB |
Output is correct |
12 |
Correct |
4 ms |
4332 KB |
Output is correct |
13 |
Correct |
4 ms |
4460 KB |
Output is correct |
14 |
Correct |
4 ms |
4460 KB |
Output is correct |
15 |
Correct |
4 ms |
4460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
559 ms |
19780 KB |
Output is correct |
2 |
Correct |
529 ms |
23060 KB |
Output is correct |
3 |
Correct |
515 ms |
22856 KB |
Output is correct |
4 |
Correct |
570 ms |
23036 KB |
Output is correct |
5 |
Correct |
524 ms |
20484 KB |
Output is correct |
6 |
Correct |
578 ms |
23660 KB |
Output is correct |
7 |
Correct |
511 ms |
22904 KB |
Output is correct |
8 |
Correct |
506 ms |
22916 KB |
Output is correct |
9 |
Correct |
583 ms |
24072 KB |
Output is correct |
10 |
Correct |
536 ms |
24092 KB |
Output is correct |
11 |
Correct |
164 ms |
12012 KB |
Output is correct |
12 |
Correct |
555 ms |
24280 KB |
Output is correct |
13 |
Correct |
558 ms |
19596 KB |
Output is correct |
14 |
Correct |
478 ms |
16980 KB |
Output is correct |
15 |
Correct |
488 ms |
22856 KB |
Output is correct |
16 |
Correct |
496 ms |
20464 KB |
Output is correct |
17 |
Correct |
496 ms |
20416 KB |
Output is correct |
18 |
Correct |
516 ms |
22828 KB |
Output is correct |
19 |
Correct |
490 ms |
20464 KB |
Output is correct |
20 |
Correct |
488 ms |
20544 KB |
Output is correct |
21 |
Correct |
500 ms |
20420 KB |
Output is correct |
22 |
Correct |
502 ms |
22604 KB |
Output is correct |
23 |
Correct |
153 ms |
11884 KB |
Output is correct |
24 |
Correct |
519 ms |
22856 KB |
Output is correct |
25 |
Correct |
39 ms |
6004 KB |
Output is correct |
26 |
Correct |
4 ms |
4460 KB |
Output is correct |
27 |
Correct |
4 ms |
4460 KB |
Output is correct |
28 |
Correct |
78 ms |
8320 KB |
Output is correct |
29 |
Correct |
40 ms |
7036 KB |
Output is correct |
30 |
Correct |
5 ms |
4480 KB |
Output is correct |
31 |
Correct |
6 ms |
4588 KB |
Output is correct |
32 |
Correct |
8 ms |
4588 KB |
Output is correct |
33 |
Correct |
5 ms |
4460 KB |
Output is correct |
34 |
Correct |
38 ms |
6944 KB |
Output is correct |
35 |
Correct |
3 ms |
4332 KB |
Output is correct |
36 |
Correct |
4 ms |
4332 KB |
Output is correct |
37 |
Correct |
4 ms |
4460 KB |
Output is correct |
38 |
Correct |
4 ms |
4460 KB |
Output is correct |
39 |
Correct |
4 ms |
4460 KB |
Output is correct |
40 |
Correct |
576 ms |
23900 KB |
Output is correct |
41 |
Correct |
580 ms |
23988 KB |
Output is correct |
42 |
Correct |
587 ms |
24040 KB |
Output is correct |
43 |
Correct |
159 ms |
12012 KB |
Output is correct |
44 |
Correct |
165 ms |
11884 KB |
Output is correct |
45 |
Correct |
511 ms |
19568 KB |
Output is correct |
46 |
Correct |
514 ms |
19404 KB |
Output is correct |
47 |
Correct |
622 ms |
20864 KB |
Output is correct |
48 |
Correct |
169 ms |
11372 KB |
Output is correct |
49 |
Correct |
597 ms |
22792 KB |
Output is correct |
50 |
Correct |
523 ms |
19740 KB |
Output is correct |
51 |
Correct |
524 ms |
19452 KB |
Output is correct |