#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pli = pair<long long, int>;
using ll = long long;
const int MN = 1e5 + 5;
vector<pii> adj[MN];
ll distU[MN], distV[MN], distS[MN], distT[MN], dpU[MN], dpV[MN];
int deg[MN];
void dijkstra (int source, long long *dist) {
priority_queue<pli,vector<pli>,greater<pli>> pq;
dist[source] = 0; pq.push({0,source});
while (!pq.empty()) {
ll d = pq.top().first; int cur = pq.top().second; pq.pop();
if (d > dist[cur]) continue;
for (pii &p : adj[cur]) if (d + p.second < dist[p.first]) {
dist[p.first] = d + p.second;
pq.push({dist[p.first],p.first});
}
}
}
int main () { //yikes
int n,m,s,t,u,v;
scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
while (m--) {
int a,b,c;
scanf ("%d %d %d",&a,&b,&c);
adj[a].emplace_back(b,c);
adj[b].emplace_back(a,c);
}
memset(distU,0x3f,sizeof distU); memset(distV,0x3f,sizeof distV); memset(distS,0x3f,sizeof distS); memset(distT,0x3f,sizeof distT);
dijkstra(u,distU); dijkstra(v,distV); dijkstra(s,distS); dijkstra(t,distT);
for (int i = 1; i <= n; i++) {
dpU[i] = distU[i]; dpV[i] = distV[i];
if (distS[i] + distT[i] == distS[t]) {
for (pii p : adj[i]) if (distS[i] + p.second == distS[p.first] && distS[p.first] + distT[p.first] == distS[t]) ++deg[p.first];
}
}
queue<int> q; q.push(s);
while (!q.empty()) {
int cur = q.front(); q.pop();
for (pii p : adj[cur]) if (distS[cur] + p.second == distS[p.first] && distS[p.first] + distT[p.first] == distS[t]) {
dpU[p.first] = min(dpU[p.first],dpU[cur]); dpV[p.first] = min(dpV[p.first],dpV[cur]);
if (!(--deg[p.first])) q.push(p.first);
}
}
ll ret = LLONG_MAX;
for (int i = 1; i <= n; i++) {
ret = min({ret,dpU[i]+distV[i],dpV[i]+distU[i]});
}
printf ("%lld\n",ret);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:24: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:27:9: 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 |
334 ms |
15204 KB |
Output is correct |
2 |
Correct |
352 ms |
14240 KB |
Output is correct |
3 |
Correct |
440 ms |
15112 KB |
Output is correct |
4 |
Correct |
360 ms |
15704 KB |
Output is correct |
5 |
Correct |
345 ms |
14280 KB |
Output is correct |
6 |
Correct |
367 ms |
15324 KB |
Output is correct |
7 |
Correct |
368 ms |
14108 KB |
Output is correct |
8 |
Correct |
331 ms |
14276 KB |
Output is correct |
9 |
Correct |
324 ms |
13932 KB |
Output is correct |
10 |
Correct |
264 ms |
13772 KB |
Output is correct |
11 |
Correct |
135 ms |
10872 KB |
Output is correct |
12 |
Correct |
364 ms |
13896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
372 ms |
14156 KB |
Output is correct |
2 |
Correct |
355 ms |
14184 KB |
Output is correct |
3 |
Correct |
390 ms |
14188 KB |
Output is correct |
4 |
Correct |
371 ms |
14176 KB |
Output is correct |
5 |
Correct |
355 ms |
14180 KB |
Output is correct |
6 |
Correct |
348 ms |
14048 KB |
Output is correct |
7 |
Correct |
401 ms |
14220 KB |
Output is correct |
8 |
Correct |
399 ms |
14184 KB |
Output is correct |
9 |
Correct |
365 ms |
14204 KB |
Output is correct |
10 |
Correct |
341 ms |
14336 KB |
Output is correct |
11 |
Correct |
130 ms |
10872 KB |
Output is correct |
12 |
Correct |
335 ms |
14132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
6528 KB |
Output is correct |
2 |
Correct |
3 ms |
5888 KB |
Output is correct |
3 |
Correct |
4 ms |
5888 KB |
Output is correct |
4 |
Correct |
22 ms |
7168 KB |
Output is correct |
5 |
Correct |
12 ms |
6528 KB |
Output is correct |
6 |
Correct |
4 ms |
5888 KB |
Output is correct |
7 |
Correct |
5 ms |
5888 KB |
Output is correct |
8 |
Correct |
5 ms |
6016 KB |
Output is correct |
9 |
Correct |
4 ms |
5888 KB |
Output is correct |
10 |
Correct |
13 ms |
6912 KB |
Output is correct |
11 |
Correct |
4 ms |
5888 KB |
Output is correct |
12 |
Correct |
4 ms |
5888 KB |
Output is correct |
13 |
Correct |
4 ms |
5888 KB |
Output is correct |
14 |
Correct |
4 ms |
5888 KB |
Output is correct |
15 |
Correct |
4 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
334 ms |
15204 KB |
Output is correct |
2 |
Correct |
352 ms |
14240 KB |
Output is correct |
3 |
Correct |
440 ms |
15112 KB |
Output is correct |
4 |
Correct |
360 ms |
15704 KB |
Output is correct |
5 |
Correct |
345 ms |
14280 KB |
Output is correct |
6 |
Correct |
367 ms |
15324 KB |
Output is correct |
7 |
Correct |
368 ms |
14108 KB |
Output is correct |
8 |
Correct |
331 ms |
14276 KB |
Output is correct |
9 |
Correct |
324 ms |
13932 KB |
Output is correct |
10 |
Correct |
264 ms |
13772 KB |
Output is correct |
11 |
Correct |
135 ms |
10872 KB |
Output is correct |
12 |
Correct |
364 ms |
13896 KB |
Output is correct |
13 |
Correct |
372 ms |
14156 KB |
Output is correct |
14 |
Correct |
355 ms |
14184 KB |
Output is correct |
15 |
Correct |
390 ms |
14188 KB |
Output is correct |
16 |
Correct |
371 ms |
14176 KB |
Output is correct |
17 |
Correct |
355 ms |
14180 KB |
Output is correct |
18 |
Correct |
348 ms |
14048 KB |
Output is correct |
19 |
Correct |
401 ms |
14220 KB |
Output is correct |
20 |
Correct |
399 ms |
14184 KB |
Output is correct |
21 |
Correct |
365 ms |
14204 KB |
Output is correct |
22 |
Correct |
341 ms |
14336 KB |
Output is correct |
23 |
Correct |
130 ms |
10872 KB |
Output is correct |
24 |
Correct |
335 ms |
14132 KB |
Output is correct |
25 |
Correct |
15 ms |
6528 KB |
Output is correct |
26 |
Correct |
3 ms |
5888 KB |
Output is correct |
27 |
Correct |
4 ms |
5888 KB |
Output is correct |
28 |
Correct |
22 ms |
7168 KB |
Output is correct |
29 |
Correct |
12 ms |
6528 KB |
Output is correct |
30 |
Correct |
4 ms |
5888 KB |
Output is correct |
31 |
Correct |
5 ms |
5888 KB |
Output is correct |
32 |
Correct |
5 ms |
6016 KB |
Output is correct |
33 |
Correct |
4 ms |
5888 KB |
Output is correct |
34 |
Correct |
13 ms |
6912 KB |
Output is correct |
35 |
Correct |
4 ms |
5888 KB |
Output is correct |
36 |
Correct |
4 ms |
5888 KB |
Output is correct |
37 |
Correct |
4 ms |
5888 KB |
Output is correct |
38 |
Correct |
4 ms |
5888 KB |
Output is correct |
39 |
Correct |
4 ms |
5888 KB |
Output is correct |
40 |
Correct |
307 ms |
19492 KB |
Output is correct |
41 |
Correct |
324 ms |
18416 KB |
Output is correct |
42 |
Correct |
320 ms |
18276 KB |
Output is correct |
43 |
Correct |
135 ms |
13048 KB |
Output is correct |
44 |
Correct |
150 ms |
13048 KB |
Output is correct |
45 |
Correct |
314 ms |
17580 KB |
Output is correct |
46 |
Correct |
305 ms |
17420 KB |
Output is correct |
47 |
Correct |
316 ms |
19060 KB |
Output is correct |
48 |
Correct |
140 ms |
12452 KB |
Output is correct |
49 |
Correct |
272 ms |
19148 KB |
Output is correct |
50 |
Correct |
339 ms |
17644 KB |
Output is correct |
51 |
Correct |
320 ms |
17624 KB |
Output is correct |