#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pl pair < ll, ll >
#define pii pair < int, pi >
#define vii vector < pi >
#define viii vector < pii >
const int N = 1e5 + 7;
const ll INF = 1e15 + 7;
ll d[5][N], ans;
ll x[N], y[N];
int s[5], us[N], c[N];
int n, m;
vii g[N];
void dijkstra (int id){
priority_queue < pair < ll, int > > pq;
pq.push(mk(0LL, s[id]));
memset(d[id], 0x3f3f3f3f, sizeof d[id]);
while(!pq.empty()){
ll dis = -pq.top().fr; int cur = pq.top().sc;
pq.pop();
if (d[id][cur] < dis)
continue;
d[id][cur] = dis;
for (pi to : g[cur]){
if (d[id][to.fr] > dis + to.sc){
d[id][to.fr] = dis + to.sc;
pq.push(mk(-d[id][to.fr], to.fr));
}
}
}
}
void calc (int v, ll dis = 0){
us[v] = 1;
for (pi to : g[v]){
if (dis + to.sc != d[1][to.fr] || dis + to.sc + d[2][to.fr] != d[1][s[2]])
continue;
if (!us[to.fr])
calc(to.fr, dis + to.sc);
else
c[to.fr]++;
}
}
void dfs (int v, int p = 0, ll a = INF, ll b = INF, ll dis = 0){
a = min(a, d[3][v]);
b = min(b, d[4][v]);
a = min(x[v], a);
b = min(y[v], b);
for (pi to : g[v]){
if (to.sc + dis != d[1][to.fr] || dis + to.sc + d[2][to.fr] != d[1][s[2]])
continue;
if (c[to.fr]){
c[to.fr]--;
x[to.fr] = min(x[to.fr], a);
y[to.fr] = min(y[to.fr], b);
}
else
dfs(to.fr, v, a, b, dis + to.sc);
}
ll r = min(a + d[4][v], b + d[3][v]);
ans = min(ans, r);
}
main (){
scanf("%d%d", &n, &m);
for (int i = 1; i <= 4; i++)
scanf("%d", &s[i]);
for (int i = 1; i <= m; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a].pb(mk(b, c));
g[b].pb(mk(a, c));
}
for (int i = 1; i <= 4; i++)
dijkstra(i);
memset(x, 0x3f3f3f3f, sizeof x);
memset(y, 0x3f3f3f3f, sizeof y);
ans = d[3][s[4]];
calc(s[1]);
dfs(s[1]);
printf("%lld", ans);
}
Compilation message
commuter_pass.cpp:78:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main (){
^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &s[i]);
~~~~~^~~~~~~~~~~~~
commuter_pass.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
16576 KB |
Output is correct |
2 |
Correct |
383 ms |
16296 KB |
Output is correct |
3 |
Correct |
432 ms |
22316 KB |
Output is correct |
4 |
Correct |
377 ms |
16620 KB |
Output is correct |
5 |
Correct |
414 ms |
16300 KB |
Output is correct |
6 |
Correct |
404 ms |
16800 KB |
Output is correct |
7 |
Correct |
416 ms |
16368 KB |
Output is correct |
8 |
Correct |
412 ms |
16332 KB |
Output is correct |
9 |
Correct |
365 ms |
15456 KB |
Output is correct |
10 |
Correct |
346 ms |
15140 KB |
Output is correct |
11 |
Correct |
152 ms |
15992 KB |
Output is correct |
12 |
Correct |
406 ms |
15356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
426 ms |
17888 KB |
Output is correct |
2 |
Correct |
426 ms |
18272 KB |
Output is correct |
3 |
Correct |
425 ms |
17800 KB |
Output is correct |
4 |
Correct |
414 ms |
18140 KB |
Output is correct |
5 |
Correct |
400 ms |
18540 KB |
Output is correct |
6 |
Correct |
414 ms |
20260 KB |
Output is correct |
7 |
Correct |
429 ms |
20908 KB |
Output is correct |
8 |
Correct |
410 ms |
18124 KB |
Output is correct |
9 |
Correct |
423 ms |
18848 KB |
Output is correct |
10 |
Correct |
476 ms |
17876 KB |
Output is correct |
11 |
Correct |
169 ms |
17656 KB |
Output is correct |
12 |
Correct |
408 ms |
20760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
8440 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
28 ms |
9464 KB |
Output is correct |
5 |
Correct |
18 ms |
8700 KB |
Output is correct |
6 |
Correct |
9 ms |
7416 KB |
Output is correct |
7 |
Correct |
9 ms |
7416 KB |
Output is correct |
8 |
Correct |
10 ms |
7544 KB |
Output is correct |
9 |
Correct |
9 ms |
7544 KB |
Output is correct |
10 |
Correct |
18 ms |
8440 KB |
Output is correct |
11 |
Correct |
9 ms |
7464 KB |
Output is correct |
12 |
Correct |
8 ms |
7416 KB |
Output is correct |
13 |
Correct |
8 ms |
7416 KB |
Output is correct |
14 |
Correct |
9 ms |
7416 KB |
Output is correct |
15 |
Correct |
9 ms |
7416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
16576 KB |
Output is correct |
2 |
Correct |
383 ms |
16296 KB |
Output is correct |
3 |
Correct |
432 ms |
22316 KB |
Output is correct |
4 |
Correct |
377 ms |
16620 KB |
Output is correct |
5 |
Correct |
414 ms |
16300 KB |
Output is correct |
6 |
Correct |
404 ms |
16800 KB |
Output is correct |
7 |
Correct |
416 ms |
16368 KB |
Output is correct |
8 |
Correct |
412 ms |
16332 KB |
Output is correct |
9 |
Correct |
365 ms |
15456 KB |
Output is correct |
10 |
Correct |
346 ms |
15140 KB |
Output is correct |
11 |
Correct |
152 ms |
15992 KB |
Output is correct |
12 |
Correct |
406 ms |
15356 KB |
Output is correct |
13 |
Correct |
426 ms |
17888 KB |
Output is correct |
14 |
Correct |
426 ms |
18272 KB |
Output is correct |
15 |
Correct |
425 ms |
17800 KB |
Output is correct |
16 |
Correct |
414 ms |
18140 KB |
Output is correct |
17 |
Correct |
400 ms |
18540 KB |
Output is correct |
18 |
Correct |
414 ms |
20260 KB |
Output is correct |
19 |
Correct |
429 ms |
20908 KB |
Output is correct |
20 |
Correct |
410 ms |
18124 KB |
Output is correct |
21 |
Correct |
423 ms |
18848 KB |
Output is correct |
22 |
Correct |
476 ms |
17876 KB |
Output is correct |
23 |
Correct |
169 ms |
17656 KB |
Output is correct |
24 |
Correct |
408 ms |
20760 KB |
Output is correct |
25 |
Correct |
19 ms |
8440 KB |
Output is correct |
26 |
Correct |
8 ms |
7416 KB |
Output is correct |
27 |
Correct |
9 ms |
7416 KB |
Output is correct |
28 |
Correct |
28 ms |
9464 KB |
Output is correct |
29 |
Correct |
18 ms |
8700 KB |
Output is correct |
30 |
Correct |
9 ms |
7416 KB |
Output is correct |
31 |
Correct |
9 ms |
7416 KB |
Output is correct |
32 |
Correct |
10 ms |
7544 KB |
Output is correct |
33 |
Correct |
9 ms |
7544 KB |
Output is correct |
34 |
Correct |
18 ms |
8440 KB |
Output is correct |
35 |
Correct |
9 ms |
7464 KB |
Output is correct |
36 |
Correct |
8 ms |
7416 KB |
Output is correct |
37 |
Correct |
8 ms |
7416 KB |
Output is correct |
38 |
Correct |
9 ms |
7416 KB |
Output is correct |
39 |
Correct |
9 ms |
7416 KB |
Output is correct |
40 |
Correct |
372 ms |
19624 KB |
Output is correct |
41 |
Correct |
361 ms |
18100 KB |
Output is correct |
42 |
Correct |
386 ms |
18300 KB |
Output is correct |
43 |
Correct |
167 ms |
16888 KB |
Output is correct |
44 |
Correct |
301 ms |
16960 KB |
Output is correct |
45 |
Correct |
394 ms |
18860 KB |
Output is correct |
46 |
Correct |
399 ms |
17868 KB |
Output is correct |
47 |
Correct |
396 ms |
18944 KB |
Output is correct |
48 |
Correct |
201 ms |
14208 KB |
Output is correct |
49 |
Correct |
318 ms |
19072 KB |
Output is correct |
50 |
Correct |
380 ms |
18024 KB |
Output is correct |
51 |
Correct |
359 ms |
18144 KB |
Output is correct |