#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
const int maxn = 2e5+10;
const ll inf = 1e18+10;
struct Edge
{
int u, v, w;
} edge[maxn];
int n, m;
int S, T, U, V;
ll dist[4][maxn];
bool mark[maxn];
ll mn[maxn];
vector<int> dag[maxn], ord;
vector<pii> grafo[maxn];
void dijkstra(int q, int s)
{
for (int i = 1; i <= n; i++)
{
dist[q][i] = inf;
mark[i] = false;
}
priority_queue<pii, vector<pii>, greater<pii>> fila;
dist[q][s] = 0;
fila.push({dist[q][s], s});
while (!fila.empty())
{
int u = fila.top().second; fila.pop();
if (mark[u]) continue;
mark[u] = true;
for (auto pp: grafo[u])
{
int v = pp.first, w = pp.second;
if (dist[q][v] > dist[q][u] + 1ll*w)
{
dist[q][v] = dist[q][u] + 1ll*w;
fila.push({dist[q][v], v});
}
}
}
}
void dfs(int u)
{
mark[u] = true;
for (auto v: dag[u])
if (!mark[v])
dfs(v);
ord.push_back(u);
}
ll get_mn(int a, int b)
{
ll ans = inf;
for (auto u: ord)
{
mn[u] = dist[b][u];
for (auto v: dag[u])
mn[u] = min(mn[u], mn[v]);
ans = min(ans, dist[a][u] + mn[u]);
}
return ans;
}
int main(void)
{
scanf("%d %d %d %d %d %d", &n, &m, &S, &T, &U, &V);
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
grafo[u].push_back({v, w});
grafo[v].push_back({u, w});
edge[i] = {u, v, w};
}
dijkstra(0, S); dijkstra(1, T);
dijkstra(2, U); dijkstra(3, V);
for (int i = 1; i <= m; i++)
{
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
if (dist[0][u] + 1LL*w + dist[1][v] == dist[0][T])
dag[u].push_back(v);
else if (dist[0][v] + 1LL*w + dist[1][u] == dist[0][T])
dag[v].push_back(u);
}
memset(mark, 0, sizeof mark);
for (int i = 1; i <= n; i++)
if (!mark[i])
dfs(i);
ll ans = min({dist[2][V], get_mn(2, 3), get_mn(3, 2)});
printf("%lld\n", ans);
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d %d %d", &n, &m, &S, &T, &U, &V);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
377 ms |
32716 KB |
Output is correct |
2 |
Correct |
392 ms |
31376 KB |
Output is correct |
3 |
Correct |
401 ms |
33972 KB |
Output is correct |
4 |
Correct |
368 ms |
32832 KB |
Output is correct |
5 |
Correct |
365 ms |
32012 KB |
Output is correct |
6 |
Correct |
380 ms |
32816 KB |
Output is correct |
7 |
Correct |
386 ms |
32332 KB |
Output is correct |
8 |
Correct |
386 ms |
32196 KB |
Output is correct |
9 |
Correct |
368 ms |
31984 KB |
Output is correct |
10 |
Correct |
333 ms |
31940 KB |
Output is correct |
11 |
Correct |
165 ms |
25588 KB |
Output is correct |
12 |
Correct |
374 ms |
31740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
379 ms |
32056 KB |
Output is correct |
2 |
Correct |
402 ms |
32244 KB |
Output is correct |
3 |
Correct |
396 ms |
32240 KB |
Output is correct |
4 |
Correct |
385 ms |
31716 KB |
Output is correct |
5 |
Correct |
399 ms |
31996 KB |
Output is correct |
6 |
Correct |
419 ms |
34136 KB |
Output is correct |
7 |
Correct |
429 ms |
34820 KB |
Output is correct |
8 |
Correct |
397 ms |
31904 KB |
Output is correct |
9 |
Correct |
388 ms |
32380 KB |
Output is correct |
10 |
Correct |
424 ms |
32292 KB |
Output is correct |
11 |
Correct |
173 ms |
26740 KB |
Output is correct |
12 |
Correct |
372 ms |
34472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
11904 KB |
Output is correct |
2 |
Correct |
10 ms |
9984 KB |
Output is correct |
3 |
Correct |
10 ms |
9984 KB |
Output is correct |
4 |
Correct |
32 ms |
13824 KB |
Output is correct |
5 |
Correct |
20 ms |
11904 KB |
Output is correct |
6 |
Correct |
12 ms |
10112 KB |
Output is correct |
7 |
Correct |
11 ms |
10240 KB |
Output is correct |
8 |
Correct |
13 ms |
10240 KB |
Output is correct |
9 |
Correct |
11 ms |
10112 KB |
Output is correct |
10 |
Correct |
20 ms |
11936 KB |
Output is correct |
11 |
Correct |
11 ms |
9984 KB |
Output is correct |
12 |
Correct |
10 ms |
9984 KB |
Output is correct |
13 |
Correct |
11 ms |
9984 KB |
Output is correct |
14 |
Correct |
11 ms |
9984 KB |
Output is correct |
15 |
Correct |
11 ms |
9984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
377 ms |
32716 KB |
Output is correct |
2 |
Correct |
392 ms |
31376 KB |
Output is correct |
3 |
Correct |
401 ms |
33972 KB |
Output is correct |
4 |
Correct |
368 ms |
32832 KB |
Output is correct |
5 |
Correct |
365 ms |
32012 KB |
Output is correct |
6 |
Correct |
380 ms |
32816 KB |
Output is correct |
7 |
Correct |
386 ms |
32332 KB |
Output is correct |
8 |
Correct |
386 ms |
32196 KB |
Output is correct |
9 |
Correct |
368 ms |
31984 KB |
Output is correct |
10 |
Correct |
333 ms |
31940 KB |
Output is correct |
11 |
Correct |
165 ms |
25588 KB |
Output is correct |
12 |
Correct |
374 ms |
31740 KB |
Output is correct |
13 |
Correct |
379 ms |
32056 KB |
Output is correct |
14 |
Correct |
402 ms |
32244 KB |
Output is correct |
15 |
Correct |
396 ms |
32240 KB |
Output is correct |
16 |
Correct |
385 ms |
31716 KB |
Output is correct |
17 |
Correct |
399 ms |
31996 KB |
Output is correct |
18 |
Correct |
419 ms |
34136 KB |
Output is correct |
19 |
Correct |
429 ms |
34820 KB |
Output is correct |
20 |
Correct |
397 ms |
31904 KB |
Output is correct |
21 |
Correct |
388 ms |
32380 KB |
Output is correct |
22 |
Correct |
424 ms |
32292 KB |
Output is correct |
23 |
Correct |
173 ms |
26740 KB |
Output is correct |
24 |
Correct |
372 ms |
34472 KB |
Output is correct |
25 |
Correct |
22 ms |
11904 KB |
Output is correct |
26 |
Correct |
10 ms |
9984 KB |
Output is correct |
27 |
Correct |
10 ms |
9984 KB |
Output is correct |
28 |
Correct |
32 ms |
13824 KB |
Output is correct |
29 |
Correct |
20 ms |
11904 KB |
Output is correct |
30 |
Correct |
12 ms |
10112 KB |
Output is correct |
31 |
Correct |
11 ms |
10240 KB |
Output is correct |
32 |
Correct |
13 ms |
10240 KB |
Output is correct |
33 |
Correct |
11 ms |
10112 KB |
Output is correct |
34 |
Correct |
20 ms |
11936 KB |
Output is correct |
35 |
Correct |
11 ms |
9984 KB |
Output is correct |
36 |
Correct |
10 ms |
9984 KB |
Output is correct |
37 |
Correct |
11 ms |
9984 KB |
Output is correct |
38 |
Correct |
11 ms |
9984 KB |
Output is correct |
39 |
Correct |
11 ms |
9984 KB |
Output is correct |
40 |
Correct |
352 ms |
32632 KB |
Output is correct |
41 |
Correct |
453 ms |
31892 KB |
Output is correct |
42 |
Correct |
369 ms |
31848 KB |
Output is correct |
43 |
Correct |
182 ms |
27888 KB |
Output is correct |
44 |
Correct |
188 ms |
27892 KB |
Output is correct |
45 |
Correct |
387 ms |
33440 KB |
Output is correct |
46 |
Correct |
441 ms |
33440 KB |
Output is correct |
47 |
Correct |
366 ms |
32600 KB |
Output is correct |
48 |
Correct |
207 ms |
25968 KB |
Output is correct |
49 |
Correct |
304 ms |
32256 KB |
Output is correct |
50 |
Correct |
361 ms |
32932 KB |
Output is correct |
51 |
Correct |
373 ms |
33628 KB |
Output is correct |