#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
const int MAX_N = 100001;
long long dists[MAX_N], distt[MAX_N], distu[MAX_N], distv[MAX_N], dp[MAX_N], dp2[MAX_N], res = 1e18;
vector<pii> edges[MAX_N];
vector<int> bef[MAX_N], bef2[MAX_N];
void dijkstra(int s, ll dist[]) {
for (int i=0; i<MAX_N; i++) dist[i] = 1e18;
dist[s] = 0;
priority_queue<pli, vector<pli>, greater<pli> > pq;
pq.push({0, s});
while (!pq.empty()) {
pli cur = pq.top();
pq.pop();
if (cur.f > dist[cur.s]) continue;
for (pii p : edges[cur.s]) {
if (dist[p.f] > dist[cur.s]+p.s) {
dist[p.f] = dist[cur.s]+p.s;
pq.push({dist[p.f], p.f});
}
}
}
}
ll ans(int x, vector<int> bef[], ll dp[]) {
if (dp[x] != 1e18) return dp[x];
dp[x]--;
for (int p : bef[x]) dp[x] = min(dp[x], ans(p, bef, dp));
return dp[x] = min(dp[x], distu[x]);
}
int main() {
int n, m, s, t, u, v, a, b, c;
scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
while (m--) {
scanf("%d%d%d", &a, &b, &c);
edges[a].emplace_back(b, c);
edges[b].emplace_back(a, c);
}
dijkstra(s, dists);
dijkstra(t, distt);
dijkstra(u, distu);
dijkstra(v, distv);
for (int i=1; i<=n; i++) {
for (pii j : edges[i]) {
if (dists[i]+j.s+distt[j.f] == dists[t]) {
bef[j.f].push_back(i);
bef2[i].push_back(j.f);
}
}
dp[i] = dp2[i] = 1e18;
}
for (int i=1; i<=n; i++) {
if (dists[i]+distt[i]==dists[t]) {
res = min(res, min(ans(i, bef, dp), ans(i, bef2, dp2))+distv[i]);
}
}
printf("%lld\n", min(res, distu[v]));
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
45 | scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%d%d%d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
357 ms |
20052 KB |
Output is correct |
2 |
Correct |
394 ms |
21576 KB |
Output is correct |
3 |
Correct |
423 ms |
25948 KB |
Output is correct |
4 |
Correct |
353 ms |
21668 KB |
Output is correct |
5 |
Correct |
380 ms |
22800 KB |
Output is correct |
6 |
Correct |
381 ms |
21552 KB |
Output is correct |
7 |
Correct |
389 ms |
23548 KB |
Output is correct |
8 |
Correct |
420 ms |
23400 KB |
Output is correct |
9 |
Correct |
351 ms |
20484 KB |
Output is correct |
10 |
Correct |
310 ms |
20312 KB |
Output is correct |
11 |
Correct |
183 ms |
22124 KB |
Output is correct |
12 |
Correct |
378 ms |
20356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
388 ms |
21172 KB |
Output is correct |
2 |
Correct |
413 ms |
21428 KB |
Output is correct |
3 |
Correct |
399 ms |
21012 KB |
Output is correct |
4 |
Correct |
396 ms |
21652 KB |
Output is correct |
5 |
Correct |
397 ms |
21624 KB |
Output is correct |
6 |
Correct |
397 ms |
24624 KB |
Output is correct |
7 |
Correct |
439 ms |
25196 KB |
Output is correct |
8 |
Correct |
418 ms |
20876 KB |
Output is correct |
9 |
Correct |
392 ms |
21748 KB |
Output is correct |
10 |
Correct |
400 ms |
21392 KB |
Output is correct |
11 |
Correct |
208 ms |
22508 KB |
Output is correct |
12 |
Correct |
398 ms |
24492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
11244 KB |
Output is correct |
2 |
Correct |
7 ms |
10476 KB |
Output is correct |
3 |
Correct |
8 ms |
10476 KB |
Output is correct |
4 |
Correct |
24 ms |
12652 KB |
Output is correct |
5 |
Correct |
16 ms |
11628 KB |
Output is correct |
6 |
Correct |
8 ms |
10604 KB |
Output is correct |
7 |
Correct |
9 ms |
10604 KB |
Output is correct |
8 |
Correct |
9 ms |
10732 KB |
Output is correct |
9 |
Correct |
8 ms |
10604 KB |
Output is correct |
10 |
Correct |
16 ms |
11628 KB |
Output is correct |
11 |
Correct |
8 ms |
10476 KB |
Output is correct |
12 |
Correct |
7 ms |
10476 KB |
Output is correct |
13 |
Correct |
8 ms |
10476 KB |
Output is correct |
14 |
Correct |
8 ms |
10604 KB |
Output is correct |
15 |
Correct |
8 ms |
10604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
357 ms |
20052 KB |
Output is correct |
2 |
Correct |
394 ms |
21576 KB |
Output is correct |
3 |
Correct |
423 ms |
25948 KB |
Output is correct |
4 |
Correct |
353 ms |
21668 KB |
Output is correct |
5 |
Correct |
380 ms |
22800 KB |
Output is correct |
6 |
Correct |
381 ms |
21552 KB |
Output is correct |
7 |
Correct |
389 ms |
23548 KB |
Output is correct |
8 |
Correct |
420 ms |
23400 KB |
Output is correct |
9 |
Correct |
351 ms |
20484 KB |
Output is correct |
10 |
Correct |
310 ms |
20312 KB |
Output is correct |
11 |
Correct |
183 ms |
22124 KB |
Output is correct |
12 |
Correct |
378 ms |
20356 KB |
Output is correct |
13 |
Correct |
388 ms |
21172 KB |
Output is correct |
14 |
Correct |
413 ms |
21428 KB |
Output is correct |
15 |
Correct |
399 ms |
21012 KB |
Output is correct |
16 |
Correct |
396 ms |
21652 KB |
Output is correct |
17 |
Correct |
397 ms |
21624 KB |
Output is correct |
18 |
Correct |
397 ms |
24624 KB |
Output is correct |
19 |
Correct |
439 ms |
25196 KB |
Output is correct |
20 |
Correct |
418 ms |
20876 KB |
Output is correct |
21 |
Correct |
392 ms |
21748 KB |
Output is correct |
22 |
Correct |
400 ms |
21392 KB |
Output is correct |
23 |
Correct |
208 ms |
22508 KB |
Output is correct |
24 |
Correct |
398 ms |
24492 KB |
Output is correct |
25 |
Correct |
16 ms |
11244 KB |
Output is correct |
26 |
Correct |
7 ms |
10476 KB |
Output is correct |
27 |
Correct |
8 ms |
10476 KB |
Output is correct |
28 |
Correct |
24 ms |
12652 KB |
Output is correct |
29 |
Correct |
16 ms |
11628 KB |
Output is correct |
30 |
Correct |
8 ms |
10604 KB |
Output is correct |
31 |
Correct |
9 ms |
10604 KB |
Output is correct |
32 |
Correct |
9 ms |
10732 KB |
Output is correct |
33 |
Correct |
8 ms |
10604 KB |
Output is correct |
34 |
Correct |
16 ms |
11628 KB |
Output is correct |
35 |
Correct |
8 ms |
10476 KB |
Output is correct |
36 |
Correct |
7 ms |
10476 KB |
Output is correct |
37 |
Correct |
8 ms |
10476 KB |
Output is correct |
38 |
Correct |
8 ms |
10604 KB |
Output is correct |
39 |
Correct |
8 ms |
10604 KB |
Output is correct |
40 |
Correct |
349 ms |
24192 KB |
Output is correct |
41 |
Correct |
351 ms |
22932 KB |
Output is correct |
42 |
Correct |
370 ms |
22888 KB |
Output is correct |
43 |
Correct |
228 ms |
26476 KB |
Output is correct |
44 |
Correct |
229 ms |
26476 KB |
Output is correct |
45 |
Correct |
427 ms |
27692 KB |
Output is correct |
46 |
Correct |
424 ms |
27424 KB |
Output is correct |
47 |
Correct |
349 ms |
23824 KB |
Output is correct |
48 |
Correct |
231 ms |
24044 KB |
Output is correct |
49 |
Correct |
301 ms |
23672 KB |
Output is correct |
50 |
Correct |
427 ms |
26356 KB |
Output is correct |
51 |
Correct |
415 ms |
27696 KB |
Output is correct |