#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define N 100005
#define inf 2000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, S, T, U, V, visited[N];
ll dist[N][5], from_u[N][5], ans = inf;
vector<pii> grafo[N];
void dijkstra(int x, int f, int flag)
{
priority_queue<pii, vector<pii>, greater<pii> > pq;
for(int i = 1; i <= n; i++) dist[i][f] = inf;
dist[x][f] = 0, pq.push(pii(0, x));
while(!pq.empty())
{
int x = pq.top().s, d = pq.top().f;
pq.pop();
for(auto v: grafo[x])
{
if(dist[v.f][f] > dist[x][f] + v.s)
{
dist[v.f][f] = dist[x][f] + v.s;
if(flag == 1) from_u[v.f][0] = min(from_u[x][0], dist[v.f][0]);
else if(flag == 2) from_u[v.f][1] = min(from_u[x][1], dist[v.f][0]);
pq.push(pii(dist[v.f][f], v.f));
}
else if(dist[v.f][f] == dist[x][f] + v.s)
{
if(flag == 1) from_u[v.f][0] = min(from_u[v.f][0], min(from_u[x][0], dist[v.f][0]));
else if(flag == 2) from_u[v.f][1] = min(from_u[v.f][1], min(from_u[x][1], dist[v.f][0]));
}
}
}
}
ll solve()
{
dijkstra(U, 0, 0), dijkstra(V, 1, 0);
for(int i = 1; i <= n; i++) from_u[i][0] = from_u[i][1] = inf;
from_u[S][0] = dist[S][0], from_u[T][1] = dist[T][0];
dijkstra(S, 2, 1), dijkstra(T, 3, 2);
for(int x = 1; x <= n; x++)
{
if(dist[x][2] + dist[x][3] == dist[T][2])
ans = min(ans, min(from_u[x][0], from_u[x][1]) + dist[x][1]);
}
return min(ans, dist[V][0]);
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m>>S>>T>>U>>V;
for(int i = 1, a, b, c; i <= m; i++)
{
cin>>a>>b>>c;
grafo[a].push_back(pii(b, c));
grafo[b].push_back(pii(a, c));
}
cout<<solve()<<"\n";
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(long long int, long long int, long long int)':
commuter_pass.cpp:27:23: warning: unused variable 'd' [-Wunused-variable]
int x = pq.top().s, d = pq.top().f;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
468 ms |
24156 KB |
Output is correct |
2 |
Correct |
549 ms |
24156 KB |
Output is correct |
3 |
Correct |
503 ms |
24156 KB |
Output is correct |
4 |
Correct |
450 ms |
24156 KB |
Output is correct |
5 |
Correct |
490 ms |
24156 KB |
Output is correct |
6 |
Correct |
535 ms |
24484 KB |
Output is correct |
7 |
Correct |
543 ms |
24484 KB |
Output is correct |
8 |
Correct |
565 ms |
24484 KB |
Output is correct |
9 |
Correct |
488 ms |
24484 KB |
Output is correct |
10 |
Correct |
428 ms |
24484 KB |
Output is correct |
11 |
Correct |
167 ms |
24484 KB |
Output is correct |
12 |
Correct |
527 ms |
24484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
597 ms |
24484 KB |
Output is correct |
2 |
Correct |
598 ms |
24484 KB |
Output is correct |
3 |
Correct |
555 ms |
24484 KB |
Output is correct |
4 |
Correct |
617 ms |
24484 KB |
Output is correct |
5 |
Correct |
532 ms |
24484 KB |
Output is correct |
6 |
Correct |
520 ms |
24484 KB |
Output is correct |
7 |
Correct |
584 ms |
24484 KB |
Output is correct |
8 |
Correct |
591 ms |
24484 KB |
Output is correct |
9 |
Correct |
591 ms |
24484 KB |
Output is correct |
10 |
Correct |
719 ms |
24484 KB |
Output is correct |
11 |
Correct |
173 ms |
24484 KB |
Output is correct |
12 |
Correct |
541 ms |
24484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
24484 KB |
Output is correct |
2 |
Correct |
4 ms |
24484 KB |
Output is correct |
3 |
Correct |
4 ms |
24484 KB |
Output is correct |
4 |
Correct |
20 ms |
24484 KB |
Output is correct |
5 |
Correct |
14 ms |
24484 KB |
Output is correct |
6 |
Correct |
4 ms |
24484 KB |
Output is correct |
7 |
Correct |
5 ms |
24484 KB |
Output is correct |
8 |
Correct |
6 ms |
24484 KB |
Output is correct |
9 |
Correct |
4 ms |
24484 KB |
Output is correct |
10 |
Correct |
13 ms |
24484 KB |
Output is correct |
11 |
Correct |
4 ms |
24484 KB |
Output is correct |
12 |
Correct |
3 ms |
24484 KB |
Output is correct |
13 |
Correct |
4 ms |
24484 KB |
Output is correct |
14 |
Correct |
4 ms |
24484 KB |
Output is correct |
15 |
Correct |
4 ms |
24484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
468 ms |
24156 KB |
Output is correct |
2 |
Correct |
549 ms |
24156 KB |
Output is correct |
3 |
Correct |
503 ms |
24156 KB |
Output is correct |
4 |
Correct |
450 ms |
24156 KB |
Output is correct |
5 |
Correct |
490 ms |
24156 KB |
Output is correct |
6 |
Correct |
535 ms |
24484 KB |
Output is correct |
7 |
Correct |
543 ms |
24484 KB |
Output is correct |
8 |
Correct |
565 ms |
24484 KB |
Output is correct |
9 |
Correct |
488 ms |
24484 KB |
Output is correct |
10 |
Correct |
428 ms |
24484 KB |
Output is correct |
11 |
Correct |
167 ms |
24484 KB |
Output is correct |
12 |
Correct |
527 ms |
24484 KB |
Output is correct |
13 |
Correct |
597 ms |
24484 KB |
Output is correct |
14 |
Correct |
598 ms |
24484 KB |
Output is correct |
15 |
Correct |
555 ms |
24484 KB |
Output is correct |
16 |
Correct |
617 ms |
24484 KB |
Output is correct |
17 |
Correct |
532 ms |
24484 KB |
Output is correct |
18 |
Correct |
520 ms |
24484 KB |
Output is correct |
19 |
Correct |
584 ms |
24484 KB |
Output is correct |
20 |
Correct |
591 ms |
24484 KB |
Output is correct |
21 |
Correct |
591 ms |
24484 KB |
Output is correct |
22 |
Correct |
719 ms |
24484 KB |
Output is correct |
23 |
Correct |
173 ms |
24484 KB |
Output is correct |
24 |
Correct |
541 ms |
24484 KB |
Output is correct |
25 |
Correct |
13 ms |
24484 KB |
Output is correct |
26 |
Correct |
4 ms |
24484 KB |
Output is correct |
27 |
Correct |
4 ms |
24484 KB |
Output is correct |
28 |
Correct |
20 ms |
24484 KB |
Output is correct |
29 |
Correct |
14 ms |
24484 KB |
Output is correct |
30 |
Correct |
4 ms |
24484 KB |
Output is correct |
31 |
Correct |
5 ms |
24484 KB |
Output is correct |
32 |
Correct |
6 ms |
24484 KB |
Output is correct |
33 |
Correct |
4 ms |
24484 KB |
Output is correct |
34 |
Correct |
13 ms |
24484 KB |
Output is correct |
35 |
Correct |
4 ms |
24484 KB |
Output is correct |
36 |
Correct |
3 ms |
24484 KB |
Output is correct |
37 |
Correct |
4 ms |
24484 KB |
Output is correct |
38 |
Correct |
4 ms |
24484 KB |
Output is correct |
39 |
Correct |
4 ms |
24484 KB |
Output is correct |
40 |
Correct |
454 ms |
24484 KB |
Output is correct |
41 |
Correct |
470 ms |
24484 KB |
Output is correct |
42 |
Correct |
495 ms |
24484 KB |
Output is correct |
43 |
Correct |
140 ms |
24484 KB |
Output is correct |
44 |
Correct |
163 ms |
24484 KB |
Output is correct |
45 |
Correct |
395 ms |
24484 KB |
Output is correct |
46 |
Correct |
407 ms |
24484 KB |
Output is correct |
47 |
Correct |
436 ms |
24484 KB |
Output is correct |
48 |
Correct |
240 ms |
24484 KB |
Output is correct |
49 |
Correct |
396 ms |
24484 KB |
Output is correct |
50 |
Correct |
410 ms |
24484 KB |
Output is correct |
51 |
Correct |
418 ms |
24484 KB |
Output is correct |