#include<bits/stdc++.h>
using namespace std ;
const int mx = 1e5 + 5 ;
const long long INF = 1e18 ;
typedef pair<long long , int> li ;
vector<pair<int,long long> > adj[mx] ;
long long dp1[mx] , dp2[mx] , dist_s[mx] , dist_t[mx] , dist_u[mx] , dist_v[mx] , ans = INF ;
int vis[mx] , n , m ;
void djikstra1(int start , long long dist[])
{
for(int i = 1 ; i <= n ; ++i) dist[i] = INF , vis[i] = 0 ;
priority_queue<li,vector<li>,greater<li> > pq ;
pq.push({0,start}) , dist[start] = 0 ;
while(!pq.empty())
{
int u = pq.top().second ;
long long cost = pq.top().first ;
pq.pop() ;
if(vis[u]) continue ;
vis[u] = 1 ;
for(auto p : adj[u])
{
int v = p.first ;
long long w = p.second ;
if(dist[v] > (cost + w))
{
dist[v] = cost + w ;
pq.push({dist[v],v}) ;
}
}
}
return ;
}
void djikstra2(int s , long long dp[] , long long dist[])
{
for(int i = 1 ; i <= n ; ++i)
{
dp[i] = dist_u[i] ;
dist[i] = INF ;
vis[i] = 0 ;
}
priority_queue<li,vector<li>,greater<li> > pq ;
pq.push({0,s}) , dist[s] = 0 ;
while(!pq.empty())
{
int u = pq.top().second ; long long cost = pq.top().first ;
pq.pop() ;
if(vis[u]) continue ;
vis[u] = 1 ;
for(auto p : adj[u])
{
int v = p.first ; long long w = p.second ;
if(dist[v] == (cost+w)) dp[v] = min(dp[v],dp[u]) ;
else if(dist[v] > (cost+w))
{
dist[v] = cost + w ;
dp[v] = min(dist_u[v],dp[u]) ;
pq.push({dist[v],v}) ;
}
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m) ;
int s , t ;
scanf("%d%d",&s,&t) ;
int u , v ;
scanf("%d%d",&u,&v) ;
for(int i = 1 ; i <= m ; ++i)
{
int a , b ;
long long c ;
scanf("%d%d%lld",&a,&b,&c) ;
adj[a].push_back({b,c}) ;
adj[b].push_back({a,c}) ;
}
djikstra1(u,dist_u) ;
djikstra1(v,dist_v) ;
djikstra2(s,dp1,dist_s) ;
djikstra2(t,dp2,dist_t) ;
for(int i = 1 ; i <= n ; ++i)
{
if(dist_s[t]==(dist_s[i] + dist_t[i]))
{
ans = min(ans,dist_v[i] + min(dp1[i],dp2[i])) ;
}
}
printf("%lld\n",min(ans,dist_u[v])) ;
return 0 ;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d%d",&n,&m) ;
| ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d%d",&s,&t) ;
| ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | scanf("%d%d",&u,&v) ;
| ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | scanf("%d%d%lld",&a,&b,&c) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
394 ms |
25192 KB |
Output is correct |
2 |
Correct |
394 ms |
23664 KB |
Output is correct |
3 |
Correct |
454 ms |
24904 KB |
Output is correct |
4 |
Correct |
383 ms |
24032 KB |
Output is correct |
5 |
Correct |
379 ms |
23284 KB |
Output is correct |
6 |
Correct |
414 ms |
25384 KB |
Output is correct |
7 |
Correct |
403 ms |
23696 KB |
Output is correct |
8 |
Correct |
417 ms |
23408 KB |
Output is correct |
9 |
Correct |
437 ms |
24304 KB |
Output is correct |
10 |
Correct |
327 ms |
24268 KB |
Output is correct |
11 |
Correct |
175 ms |
15212 KB |
Output is correct |
12 |
Correct |
432 ms |
24188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
445 ms |
23752 KB |
Output is correct |
2 |
Correct |
445 ms |
23756 KB |
Output is correct |
3 |
Correct |
412 ms |
23644 KB |
Output is correct |
4 |
Correct |
447 ms |
23540 KB |
Output is correct |
5 |
Correct |
408 ms |
23628 KB |
Output is correct |
6 |
Correct |
409 ms |
23876 KB |
Output is correct |
7 |
Correct |
444 ms |
23512 KB |
Output is correct |
8 |
Correct |
452 ms |
23520 KB |
Output is correct |
9 |
Correct |
403 ms |
23500 KB |
Output is correct |
10 |
Correct |
430 ms |
23632 KB |
Output is correct |
11 |
Correct |
205 ms |
15212 KB |
Output is correct |
12 |
Correct |
412 ms |
23980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
4460 KB |
Output is correct |
2 |
Correct |
2 ms |
2796 KB |
Output is correct |
3 |
Correct |
2 ms |
2796 KB |
Output is correct |
4 |
Correct |
20 ms |
6124 KB |
Output is correct |
5 |
Correct |
11 ms |
4460 KB |
Output is correct |
6 |
Correct |
3 ms |
2796 KB |
Output is correct |
7 |
Correct |
4 ms |
2924 KB |
Output is correct |
8 |
Correct |
4 ms |
2924 KB |
Output is correct |
9 |
Correct |
3 ms |
2796 KB |
Output is correct |
10 |
Correct |
13 ms |
4460 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
2 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 |
394 ms |
25192 KB |
Output is correct |
2 |
Correct |
394 ms |
23664 KB |
Output is correct |
3 |
Correct |
454 ms |
24904 KB |
Output is correct |
4 |
Correct |
383 ms |
24032 KB |
Output is correct |
5 |
Correct |
379 ms |
23284 KB |
Output is correct |
6 |
Correct |
414 ms |
25384 KB |
Output is correct |
7 |
Correct |
403 ms |
23696 KB |
Output is correct |
8 |
Correct |
417 ms |
23408 KB |
Output is correct |
9 |
Correct |
437 ms |
24304 KB |
Output is correct |
10 |
Correct |
327 ms |
24268 KB |
Output is correct |
11 |
Correct |
175 ms |
15212 KB |
Output is correct |
12 |
Correct |
432 ms |
24188 KB |
Output is correct |
13 |
Correct |
445 ms |
23752 KB |
Output is correct |
14 |
Correct |
445 ms |
23756 KB |
Output is correct |
15 |
Correct |
412 ms |
23644 KB |
Output is correct |
16 |
Correct |
447 ms |
23540 KB |
Output is correct |
17 |
Correct |
408 ms |
23628 KB |
Output is correct |
18 |
Correct |
409 ms |
23876 KB |
Output is correct |
19 |
Correct |
444 ms |
23512 KB |
Output is correct |
20 |
Correct |
452 ms |
23520 KB |
Output is correct |
21 |
Correct |
403 ms |
23500 KB |
Output is correct |
22 |
Correct |
430 ms |
23632 KB |
Output is correct |
23 |
Correct |
205 ms |
15212 KB |
Output is correct |
24 |
Correct |
412 ms |
23980 KB |
Output is correct |
25 |
Correct |
12 ms |
4460 KB |
Output is correct |
26 |
Correct |
2 ms |
2796 KB |
Output is correct |
27 |
Correct |
2 ms |
2796 KB |
Output is correct |
28 |
Correct |
20 ms |
6124 KB |
Output is correct |
29 |
Correct |
11 ms |
4460 KB |
Output is correct |
30 |
Correct |
3 ms |
2796 KB |
Output is correct |
31 |
Correct |
4 ms |
2924 KB |
Output is correct |
32 |
Correct |
4 ms |
2924 KB |
Output is correct |
33 |
Correct |
3 ms |
2796 KB |
Output is correct |
34 |
Correct |
13 ms |
4460 KB |
Output is correct |
35 |
Correct |
2 ms |
2796 KB |
Output is correct |
36 |
Correct |
2 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 |
391 ms |
25216 KB |
Output is correct |
41 |
Correct |
411 ms |
24336 KB |
Output is correct |
42 |
Correct |
414 ms |
24296 KB |
Output is correct |
43 |
Correct |
188 ms |
15084 KB |
Output is correct |
44 |
Correct |
176 ms |
15084 KB |
Output is correct |
45 |
Correct |
361 ms |
23092 KB |
Output is correct |
46 |
Correct |
376 ms |
22832 KB |
Output is correct |
47 |
Correct |
387 ms |
25172 KB |
Output is correct |
48 |
Correct |
190 ms |
14572 KB |
Output is correct |
49 |
Correct |
336 ms |
24840 KB |
Output is correct |
50 |
Correct |
382 ms |
23376 KB |
Output is correct |
51 |
Correct |
430 ms |
23104 KB |
Output is correct |