#include <bits/stdc++.h>
#define pli pair<long long, int>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
vector<pli> g[N];
int n, m, u, v, s, t;
long long ds[N], dt[N], du[N], dv[N];
priority_queue<pli, vector<pli>, greater<pli> > q;
void shortest( int st, long long d[] ) {
fill( d, d+N, 1e18 );
d[st] = 0;
q.emplace( pli( 0, st ) );
while( !q.empty() ) {
long long di = q.top().x; int u = q.top().y; q.pop();
//cout << st << " " << u << " " << di << endl;
for( pli v : g[u] ) if( d[v.x] > di + v.y ) q.emplace( pli( d[v.x] = di + v.y, v.x ) );
}
}
long long solve( int a, int b, long long da[], long long db[] ) {
long long dp[N], len = da[b], ret = 1e18;
bool chk[N];
memset( chk, 0, sizeof chk );
for( int i = 1 ; i <= n ; i++ ) dp[i] = du[i];
//for( int i = 1 ; i <= n ; i++ ) cout << dp[i] << endl;
q.emplace( pli( 0, a ) ), chk[a] = true;
while( !q.empty() ) {
pli now = q.top(); q.pop();
if( now.x != da[now.y] ) continue;
long long di;
int u;
tie( di, u ) = now;
for( pli v : g[u] ) if( di + v.y + db[v.x] == len ) {
dp[v.x] = min( dp[v.x], dp[u] );
if( !chk[v.x] ) chk[v.x] = true, q.emplace( pli( di + v.y, v.x ) );
}
}
for( int i = 1 ; i <= n ; i++ ) if( da[i] + db[i] == len ) ret = min( ret, dp[i] + dv[i] );
return ret;
}
int main()
{
scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
for( int i = 1, a, b ; i <= m ; i++ ) {
long long c;
scanf("%d %d %lld",&a,&b,&c);
g[a].emplace_back( pli( b, c ) ), g[b].emplace_back( pli( a, c ) );
}
shortest( s, ds ), shortest( t, dt ), shortest( u, du ), shortest( v, dv );
printf("%lld",min( du[v], min( solve( s, t, ds, dt ), solve( t, s, dt, ds ) ) ) );
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51:10: 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:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&a,&b,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
381 ms |
18292 KB |
Output is correct |
2 |
Correct |
434 ms |
18540 KB |
Output is correct |
3 |
Correct |
420 ms |
18148 KB |
Output is correct |
4 |
Correct |
374 ms |
18536 KB |
Output is correct |
5 |
Correct |
394 ms |
18024 KB |
Output is correct |
6 |
Correct |
420 ms |
18404 KB |
Output is correct |
7 |
Correct |
424 ms |
18024 KB |
Output is correct |
8 |
Correct |
447 ms |
18280 KB |
Output is correct |
9 |
Correct |
369 ms |
18028 KB |
Output is correct |
10 |
Correct |
305 ms |
17896 KB |
Output is correct |
11 |
Correct |
164 ms |
11896 KB |
Output is correct |
12 |
Correct |
418 ms |
18024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
450 ms |
18160 KB |
Output is correct |
2 |
Correct |
452 ms |
18280 KB |
Output is correct |
3 |
Correct |
428 ms |
18032 KB |
Output is correct |
4 |
Correct |
447 ms |
18328 KB |
Output is correct |
5 |
Correct |
441 ms |
18032 KB |
Output is correct |
6 |
Correct |
435 ms |
18280 KB |
Output is correct |
7 |
Correct |
450 ms |
18028 KB |
Output is correct |
8 |
Correct |
439 ms |
18032 KB |
Output is correct |
9 |
Correct |
452 ms |
18032 KB |
Output is correct |
10 |
Correct |
446 ms |
18160 KB |
Output is correct |
11 |
Correct |
174 ms |
11896 KB |
Output is correct |
12 |
Correct |
441 ms |
18160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
7160 KB |
Output is correct |
2 |
Correct |
9 ms |
5880 KB |
Output is correct |
3 |
Correct |
8 ms |
5880 KB |
Output is correct |
4 |
Correct |
28 ms |
8440 KB |
Output is correct |
5 |
Correct |
21 ms |
7160 KB |
Output is correct |
6 |
Correct |
9 ms |
6008 KB |
Output is correct |
7 |
Correct |
9 ms |
6008 KB |
Output is correct |
8 |
Correct |
10 ms |
6136 KB |
Output is correct |
9 |
Correct |
9 ms |
6008 KB |
Output is correct |
10 |
Correct |
23 ms |
7256 KB |
Output is correct |
11 |
Correct |
8 ms |
5884 KB |
Output is correct |
12 |
Correct |
8 ms |
5880 KB |
Output is correct |
13 |
Correct |
8 ms |
5880 KB |
Output is correct |
14 |
Correct |
8 ms |
6008 KB |
Output is correct |
15 |
Correct |
9 ms |
6008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
381 ms |
18292 KB |
Output is correct |
2 |
Correct |
434 ms |
18540 KB |
Output is correct |
3 |
Correct |
420 ms |
18148 KB |
Output is correct |
4 |
Correct |
374 ms |
18536 KB |
Output is correct |
5 |
Correct |
394 ms |
18024 KB |
Output is correct |
6 |
Correct |
420 ms |
18404 KB |
Output is correct |
7 |
Correct |
424 ms |
18024 KB |
Output is correct |
8 |
Correct |
447 ms |
18280 KB |
Output is correct |
9 |
Correct |
369 ms |
18028 KB |
Output is correct |
10 |
Correct |
305 ms |
17896 KB |
Output is correct |
11 |
Correct |
164 ms |
11896 KB |
Output is correct |
12 |
Correct |
418 ms |
18024 KB |
Output is correct |
13 |
Correct |
450 ms |
18160 KB |
Output is correct |
14 |
Correct |
452 ms |
18280 KB |
Output is correct |
15 |
Correct |
428 ms |
18032 KB |
Output is correct |
16 |
Correct |
447 ms |
18328 KB |
Output is correct |
17 |
Correct |
441 ms |
18032 KB |
Output is correct |
18 |
Correct |
435 ms |
18280 KB |
Output is correct |
19 |
Correct |
450 ms |
18028 KB |
Output is correct |
20 |
Correct |
439 ms |
18032 KB |
Output is correct |
21 |
Correct |
452 ms |
18032 KB |
Output is correct |
22 |
Correct |
446 ms |
18160 KB |
Output is correct |
23 |
Correct |
174 ms |
11896 KB |
Output is correct |
24 |
Correct |
441 ms |
18160 KB |
Output is correct |
25 |
Correct |
18 ms |
7160 KB |
Output is correct |
26 |
Correct |
9 ms |
5880 KB |
Output is correct |
27 |
Correct |
8 ms |
5880 KB |
Output is correct |
28 |
Correct |
28 ms |
8440 KB |
Output is correct |
29 |
Correct |
21 ms |
7160 KB |
Output is correct |
30 |
Correct |
9 ms |
6008 KB |
Output is correct |
31 |
Correct |
9 ms |
6008 KB |
Output is correct |
32 |
Correct |
10 ms |
6136 KB |
Output is correct |
33 |
Correct |
9 ms |
6008 KB |
Output is correct |
34 |
Correct |
23 ms |
7256 KB |
Output is correct |
35 |
Correct |
8 ms |
5884 KB |
Output is correct |
36 |
Correct |
8 ms |
5880 KB |
Output is correct |
37 |
Correct |
8 ms |
5880 KB |
Output is correct |
38 |
Correct |
8 ms |
6008 KB |
Output is correct |
39 |
Correct |
9 ms |
6008 KB |
Output is correct |
40 |
Correct |
360 ms |
17888 KB |
Output is correct |
41 |
Correct |
385 ms |
18156 KB |
Output is correct |
42 |
Correct |
366 ms |
18032 KB |
Output is correct |
43 |
Correct |
182 ms |
11896 KB |
Output is correct |
44 |
Correct |
186 ms |
11952 KB |
Output is correct |
45 |
Correct |
419 ms |
17756 KB |
Output is correct |
46 |
Correct |
422 ms |
17768 KB |
Output is correct |
47 |
Correct |
364 ms |
18276 KB |
Output is correct |
48 |
Correct |
188 ms |
11896 KB |
Output is correct |
49 |
Correct |
290 ms |
17888 KB |
Output is correct |
50 |
Correct |
404 ms |
17904 KB |
Output is correct |
51 |
Correct |
396 ms |
17896 KB |
Output is correct |