#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
using pii=pair<int, int>;
#define f first
#define s second
const int MAXN = 100005;
#define pb push_back
#define mp make_pair
int n, m;
vector<pii> adj[MAXN];
ll wt[MAXN], dis_U[MAXN], dis_V[MAXN], dis_S[MAXN];
bool vis[MAXN];
ll ans;
/// Set-based Dijkstra implementation.
void dijk(int src)
{
fill(wt, wt + n, 1e15+7);
fill(vis, vis+n, 0);
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(mp(0, src));
wt[src] = 0;
int ct = 0;
while (!pq.empty())
{
pii tp = pq.top();
pq.pop();
if(vis[tp.s]) continue;
vis[tp.s] = 1;
for (pii gu : adj[tp.s])
{
int w = gu.f;
int ind = gu.s;
if (wt[tp.s] + w < wt[ind])
{
wt[ind] = wt[tp.s] + w;
pq.push(mp(wt[ind], ind));
}
}
}
}
ll dp_U[MAXN], dp_V[MAXN];
void dijk_dp(int src, int dest)
{
fill(dis_S, dis_S+n, 1e15+7);
fill(dp_U, dp_U+n, 1e15+7);
fill(dp_V, dp_V+n, 1e15+7);
fill(vis, vis+n, 0);
dis_S[src] = 0;
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
pq.push(mp(0, mp(src, -1)));
while(!pq.empty())
{
pair<int, pii> tp = pq.top(); pq.pop();
int w = tp.f;
int nd = tp.s.f;
int par = tp.s.s;
if(!vis[nd])
{
vis[nd] = 1;
dis_S[nd] = w;
if(par >= 0) dp_U[nd] = min(dp_U[par], dis_U[nd]);
else dp_U[nd] = dis_U[nd];
if(par >= 0) dp_V[nd] = min(dp_V[par], dis_V[nd]);
else dp_V[nd] = dis_V[nd];
for(auto x : adj[nd])
{
pq.push(mp(w+x.f, mp(x.s,nd)));
}
} else if(w == dis_S[nd])
{
if(par >= 0 && min(dis_U[nd], dp_U[par]) + min(dis_V[nd], dp_V[par]) <= dp_U[nd]+dp_V[nd])
{
dp_U[nd] = min(dis_U[nd], dp_U[par]);
dp_V[nd] = min(dis_V[nd], dp_V[par]);
}
}
}
ans = min(ans, dp_U[dest] + dp_V[dest]);
}
signed main()
{
cin >> n >> m;
int S, T, U, V; cin >> S >> T >> U >> V;
--S; --T; --U; --V;
for(int i = 0; i < m; i++)
{
int a, b, w; cin >> a >> b >> w;
--a; --b;
adj[a].pb(mp(w, b));
adj[b].pb(mp(w, a));
}
dijk(U);
for(int i = 0; i < n; i++) dis_U[i] = wt[i];
dijk(V);
for(int i = 0; i < n; i++) dis_V[i] = wt[i];
ans = dis_U[V];
dijk_dp(S, T);
dijk_dp(T, S);
cout << ans << endl;
}
Compilation message
commuter_pass.cpp: In function 'void dijk(ll)':
commuter_pass.cpp:31:6: warning: unused variable 'ct' [-Wunused-variable]
31 | int ct = 0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
691 ms |
28184 KB |
Output is correct |
2 |
Correct |
614 ms |
27736 KB |
Output is correct |
3 |
Correct |
632 ms |
27336 KB |
Output is correct |
4 |
Correct |
696 ms |
27276 KB |
Output is correct |
5 |
Correct |
598 ms |
24036 KB |
Output is correct |
6 |
Correct |
690 ms |
27928 KB |
Output is correct |
7 |
Correct |
614 ms |
27508 KB |
Output is correct |
8 |
Correct |
639 ms |
27832 KB |
Output is correct |
9 |
Correct |
698 ms |
28068 KB |
Output is correct |
10 |
Correct |
633 ms |
32328 KB |
Output is correct |
11 |
Correct |
249 ms |
14828 KB |
Output is correct |
12 |
Correct |
697 ms |
32308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
676 ms |
27768 KB |
Output is correct |
2 |
Correct |
608 ms |
23936 KB |
Output is correct |
3 |
Correct |
630 ms |
27140 KB |
Output is correct |
4 |
Correct |
611 ms |
24064 KB |
Output is correct |
5 |
Correct |
596 ms |
23920 KB |
Output is correct |
6 |
Correct |
605 ms |
27036 KB |
Output is correct |
7 |
Correct |
589 ms |
23796 KB |
Output is correct |
8 |
Correct |
608 ms |
23964 KB |
Output is correct |
9 |
Correct |
600 ms |
23796 KB |
Output is correct |
10 |
Correct |
602 ms |
27236 KB |
Output is correct |
11 |
Correct |
247 ms |
12652 KB |
Output is correct |
12 |
Correct |
618 ms |
27240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
5320 KB |
Output is correct |
2 |
Correct |
3 ms |
2796 KB |
Output is correct |
3 |
Correct |
3 ms |
2796 KB |
Output is correct |
4 |
Correct |
80 ms |
8016 KB |
Output is correct |
5 |
Correct |
40 ms |
6428 KB |
Output is correct |
6 |
Correct |
4 ms |
2924 KB |
Output is correct |
7 |
Correct |
6 ms |
3052 KB |
Output is correct |
8 |
Correct |
7 ms |
3124 KB |
Output is correct |
9 |
Correct |
4 ms |
2924 KB |
Output is correct |
10 |
Correct |
40 ms |
6372 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 ms |
2796 KB |
Output is correct |
13 |
Correct |
3 ms |
2796 KB |
Output is correct |
14 |
Correct |
4 ms |
2924 KB |
Output is correct |
15 |
Correct |
4 ms |
2924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
691 ms |
28184 KB |
Output is correct |
2 |
Correct |
614 ms |
27736 KB |
Output is correct |
3 |
Correct |
632 ms |
27336 KB |
Output is correct |
4 |
Correct |
696 ms |
27276 KB |
Output is correct |
5 |
Correct |
598 ms |
24036 KB |
Output is correct |
6 |
Correct |
690 ms |
27928 KB |
Output is correct |
7 |
Correct |
614 ms |
27508 KB |
Output is correct |
8 |
Correct |
639 ms |
27832 KB |
Output is correct |
9 |
Correct |
698 ms |
28068 KB |
Output is correct |
10 |
Correct |
633 ms |
32328 KB |
Output is correct |
11 |
Correct |
249 ms |
14828 KB |
Output is correct |
12 |
Correct |
697 ms |
32308 KB |
Output is correct |
13 |
Correct |
676 ms |
27768 KB |
Output is correct |
14 |
Correct |
608 ms |
23936 KB |
Output is correct |
15 |
Correct |
630 ms |
27140 KB |
Output is correct |
16 |
Correct |
611 ms |
24064 KB |
Output is correct |
17 |
Correct |
596 ms |
23920 KB |
Output is correct |
18 |
Correct |
605 ms |
27036 KB |
Output is correct |
19 |
Correct |
589 ms |
23796 KB |
Output is correct |
20 |
Correct |
608 ms |
23964 KB |
Output is correct |
21 |
Correct |
600 ms |
23796 KB |
Output is correct |
22 |
Correct |
602 ms |
27236 KB |
Output is correct |
23 |
Correct |
247 ms |
12652 KB |
Output is correct |
24 |
Correct |
618 ms |
27240 KB |
Output is correct |
25 |
Correct |
42 ms |
5320 KB |
Output is correct |
26 |
Correct |
3 ms |
2796 KB |
Output is correct |
27 |
Correct |
3 ms |
2796 KB |
Output is correct |
28 |
Correct |
80 ms |
8016 KB |
Output is correct |
29 |
Correct |
40 ms |
6428 KB |
Output is correct |
30 |
Correct |
4 ms |
2924 KB |
Output is correct |
31 |
Correct |
6 ms |
3052 KB |
Output is correct |
32 |
Correct |
7 ms |
3124 KB |
Output is correct |
33 |
Correct |
4 ms |
2924 KB |
Output is correct |
34 |
Correct |
40 ms |
6372 KB |
Output is correct |
35 |
Correct |
2 ms |
2796 KB |
Output is correct |
36 |
Correct |
2 ms |
2796 KB |
Output is correct |
37 |
Correct |
3 ms |
2796 KB |
Output is correct |
38 |
Correct |
4 ms |
2924 KB |
Output is correct |
39 |
Correct |
4 ms |
2924 KB |
Output is correct |
40 |
Correct |
653 ms |
32040 KB |
Output is correct |
41 |
Correct |
659 ms |
32080 KB |
Output is correct |
42 |
Correct |
664 ms |
32260 KB |
Output is correct |
43 |
Correct |
273 ms |
14828 KB |
Output is correct |
44 |
Correct |
240 ms |
14956 KB |
Output is correct |
45 |
Correct |
604 ms |
26260 KB |
Output is correct |
46 |
Correct |
585 ms |
25840 KB |
Output is correct |
47 |
Correct |
653 ms |
27448 KB |
Output is correct |
48 |
Correct |
227 ms |
14316 KB |
Output is correct |
49 |
Correct |
603 ms |
30188 KB |
Output is correct |
50 |
Correct |
604 ms |
26028 KB |
Output is correct |
51 |
Correct |
572 ms |
26040 KB |
Output is correct |