#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;
vector <pair <int, int>> adj[N];
long long f[N];
long long g[N];
long long dis[2][N];
long long dp[2][N];
long long invdp[2][N];
vector <int> order;
int n,m,s,t,u,v;
bool vis[N];
template <typename T>
bool mini(T &a, T b)
{
if (a > b) {
a = b;
return true;
}
return false;
}
void dijkstra(int s, long long dis[])
{
for (int i = 1; i <= n; i++)
dis[i] = oo;
dis[s] = 0;
priority_queue <pair <long long, int>> heap;
heap.push(mp(0, s));
while (heap.size()) {
int u = heap.top().se;
long long cur = -heap.top().fi;
heap.pop();
if (dis[u] != cur)
continue;
for (pair <int, int> e : adj[u])
if (mini(dis[e.fi], cur + e.se))
heap.push(mp(-dis[e.fi], e.fi));
}
}
void dfs(int u)
{
vis[u] = true;
for (pair <int, int> e : adj[u]) {
int v = e.fi;
int w = e.se;
if (!vis[v] && f[u] + g[v] + w == f[t])
dfs(v);
}
order.push_back(u);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("file.inp","r",stdin);
cin >> n >> m;
cin >> s >> t >> u >> v;
for (int i = 1; i <= m; i++) {
int u,v,w;
cin >> u >> v >> w;
adj[u].push_back(mp(v, w));
adj[v].push_back(mp(u, w));
}
dijkstra(s, f);
dijkstra(t, g);
dijkstra(u, dis[0]);
dijkstra(v, dis[1]);
dfs(s);
reverse(order.begin(), order.end());
for (int j = 0; j <= 1; j++)
for (int i = 1; i <= n; i++)
dp[j][i] = oo;
for (int i : order) {
for (int j = 0; j <= 1; j++) {
dp[j][i] = dis[j][i];
for (pair <int, int> e : adj[i]) {
int pre = e.fi;
int w = e.se;
if (f[pre] + g[i] + w == f[t])
dp[j][i] = min(dp[j][i], dp[j][pre]);
}
}
}
reverse(order.begin(), order.end());
for (int i : order) {
for (int j = 0; j <= 1; j++) {
invdp[j][i] = dis[j][i];
for (pair <int, int> e : adj[i]) {
int pre = e.fi;
int w = e.se;
if (f[i] + g[pre] + w == f[t])
invdp[j][i] = min(invdp[j][i], invdp[j][pre]);
}
}
}
long long ans = dis[0][v];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 1; j++)
ans = min(ans, dp[j][i] + invdp[j ^ 1][i]);
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
342 ms |
16840 KB |
Output is correct |
2 |
Correct |
335 ms |
17084 KB |
Output is correct |
3 |
Correct |
395 ms |
24864 KB |
Output is correct |
4 |
Correct |
325 ms |
18948 KB |
Output is correct |
5 |
Correct |
353 ms |
19248 KB |
Output is correct |
6 |
Correct |
338 ms |
19136 KB |
Output is correct |
7 |
Correct |
354 ms |
19492 KB |
Output is correct |
8 |
Correct |
366 ms |
19304 KB |
Output is correct |
9 |
Correct |
350 ms |
18420 KB |
Output is correct |
10 |
Correct |
253 ms |
18264 KB |
Output is correct |
11 |
Correct |
148 ms |
17128 KB |
Output is correct |
12 |
Correct |
355 ms |
18188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
357 ms |
18744 KB |
Output is correct |
2 |
Correct |
404 ms |
19184 KB |
Output is correct |
3 |
Correct |
354 ms |
18552 KB |
Output is correct |
4 |
Correct |
351 ms |
18952 KB |
Output is correct |
5 |
Correct |
374 ms |
19556 KB |
Output is correct |
6 |
Correct |
365 ms |
20920 KB |
Output is correct |
7 |
Correct |
397 ms |
21620 KB |
Output is correct |
8 |
Correct |
378 ms |
18928 KB |
Output is correct |
9 |
Correct |
360 ms |
19748 KB |
Output is correct |
10 |
Correct |
368 ms |
18676 KB |
Output is correct |
11 |
Correct |
157 ms |
17896 KB |
Output is correct |
12 |
Correct |
405 ms |
21356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
3820 KB |
Output is correct |
2 |
Correct |
4 ms |
2796 KB |
Output is correct |
3 |
Correct |
3 ms |
2796 KB |
Output is correct |
4 |
Correct |
18 ms |
4844 KB |
Output is correct |
5 |
Correct |
10 ms |
3820 KB |
Output is correct |
6 |
Correct |
4 ms |
2816 KB |
Output is correct |
7 |
Correct |
4 ms |
2924 KB |
Output is correct |
8 |
Correct |
5 ms |
2924 KB |
Output is correct |
9 |
Correct |
4 ms |
2796 KB |
Output is correct |
10 |
Correct |
10 ms |
3820 KB |
Output is correct |
11 |
Correct |
3 ms |
2796 KB |
Output is correct |
12 |
Correct |
3 ms |
2796 KB |
Output is correct |
13 |
Correct |
3 ms |
2796 KB |
Output is correct |
14 |
Correct |
3 ms |
2796 KB |
Output is correct |
15 |
Correct |
3 ms |
2796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
342 ms |
16840 KB |
Output is correct |
2 |
Correct |
335 ms |
17084 KB |
Output is correct |
3 |
Correct |
395 ms |
24864 KB |
Output is correct |
4 |
Correct |
325 ms |
18948 KB |
Output is correct |
5 |
Correct |
353 ms |
19248 KB |
Output is correct |
6 |
Correct |
338 ms |
19136 KB |
Output is correct |
7 |
Correct |
354 ms |
19492 KB |
Output is correct |
8 |
Correct |
366 ms |
19304 KB |
Output is correct |
9 |
Correct |
350 ms |
18420 KB |
Output is correct |
10 |
Correct |
253 ms |
18264 KB |
Output is correct |
11 |
Correct |
148 ms |
17128 KB |
Output is correct |
12 |
Correct |
355 ms |
18188 KB |
Output is correct |
13 |
Correct |
357 ms |
18744 KB |
Output is correct |
14 |
Correct |
404 ms |
19184 KB |
Output is correct |
15 |
Correct |
354 ms |
18552 KB |
Output is correct |
16 |
Correct |
351 ms |
18952 KB |
Output is correct |
17 |
Correct |
374 ms |
19556 KB |
Output is correct |
18 |
Correct |
365 ms |
20920 KB |
Output is correct |
19 |
Correct |
397 ms |
21620 KB |
Output is correct |
20 |
Correct |
378 ms |
18928 KB |
Output is correct |
21 |
Correct |
360 ms |
19748 KB |
Output is correct |
22 |
Correct |
368 ms |
18676 KB |
Output is correct |
23 |
Correct |
157 ms |
17896 KB |
Output is correct |
24 |
Correct |
405 ms |
21356 KB |
Output is correct |
25 |
Correct |
14 ms |
3820 KB |
Output is correct |
26 |
Correct |
4 ms |
2796 KB |
Output is correct |
27 |
Correct |
3 ms |
2796 KB |
Output is correct |
28 |
Correct |
18 ms |
4844 KB |
Output is correct |
29 |
Correct |
10 ms |
3820 KB |
Output is correct |
30 |
Correct |
4 ms |
2816 KB |
Output is correct |
31 |
Correct |
4 ms |
2924 KB |
Output is correct |
32 |
Correct |
5 ms |
2924 KB |
Output is correct |
33 |
Correct |
4 ms |
2796 KB |
Output is correct |
34 |
Correct |
10 ms |
3820 KB |
Output is correct |
35 |
Correct |
3 ms |
2796 KB |
Output is correct |
36 |
Correct |
3 ms |
2796 KB |
Output is correct |
37 |
Correct |
3 ms |
2796 KB |
Output is correct |
38 |
Correct |
3 ms |
2796 KB |
Output is correct |
39 |
Correct |
3 ms |
2796 KB |
Output is correct |
40 |
Correct |
313 ms |
19440 KB |
Output is correct |
41 |
Correct |
332 ms |
18324 KB |
Output is correct |
42 |
Correct |
313 ms |
18276 KB |
Output is correct |
43 |
Correct |
202 ms |
17972 KB |
Output is correct |
44 |
Correct |
160 ms |
18020 KB |
Output is correct |
45 |
Correct |
389 ms |
19628 KB |
Output is correct |
46 |
Correct |
362 ms |
19496 KB |
Output is correct |
47 |
Correct |
309 ms |
18960 KB |
Output is correct |
48 |
Correct |
179 ms |
15332 KB |
Output is correct |
49 |
Correct |
281 ms |
19064 KB |
Output is correct |
50 |
Correct |
399 ms |
19568 KB |
Output is correct |
51 |
Correct |
362 ms |
19800 KB |
Output is correct |