# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41586 | 2018-02-19T14:15:06 Z | chonka | Commuter Pass (JOI18_commuter_pass) | C++ | 589 ms | 20004 KB |
#include<iostream> #include<stdio.h> #include<vector> #include<queue> using namespace std ; #define MAXN 200007 long long inf ; int n , m ; int p1 , p2 ; int p3 , p4 ; vector < pair < int , int > > v[ MAXN ] ; long long f[ MAXN ][ 5 ] ; long long dp[ MAXN ][ 3 ] ; struct tuhla { int vertex ; long long cost ; tuhla ( ) { vertex = cost = 0 ; } tuhla ( int _vertex , long long _cost ) { vertex = _vertex ; cost = _cost ; } }; bool operator < ( tuhla aux1 , tuhla aux2 ) { return ( aux1.cost > aux2.cost ) ; } priority_queue < tuhla > q ; void dijkstra ( int vertex , int id ) { int i ; for ( i = 1 ; i <= n ; i ++ ) { f[ i ][ id ] = inf ; } f[ vertex ][ id ] = 0 ; q.push ( tuhla ( vertex , 0 ) ) ; while ( q.empty ( ) == false ) { tuhla u = q.top ( ) ; q.pop ( ) ; if ( u.cost != f[ u.vertex ][ id ] ) { continue ; } int sz = v[ u.vertex ].size ( ) ; for ( i = 0 ; i < sz ; i ++ ) { int h = v[ u.vertex ][ i ].first ; int c = v[ u.vertex ][ i ].second ; if ( f[ h ][ id ] > u.cost + c ) { f[ h ][ id ] = u.cost + c ; q.push ( tuhla ( h , f[ h ][ id ] ) ) ; } } } } void calc_dp ( int vertex , int id , int pos ) { int i ; for ( i = 1 ; i <= n ; i ++ ) { f[ i ][ id ] = inf ; dp[ i ][ pos ] = inf ; } f[ vertex ][ id ] = 0 ; dp[ vertex ][ pos ] = f[ vertex ][ 2 ] ; q.push ( tuhla ( vertex , 0 ) ) ; while ( q.empty ( ) == false ) { tuhla u = q.top ( ) ; q.pop ( ) ; if ( u.cost != f[ u.vertex ][ id ] ) { continue ; } int sz = v[ u.vertex ].size ( ) ; for ( i = 0 ; i < sz ; i ++ ) { int h = v[ u.vertex ][ i ].first ; int c = v[ u.vertex ][ i ].second ; if ( f[ h ][ id ] > u.cost + c ) { f[ h ][ id ] = u.cost + c ; q.push ( tuhla ( h , f[ h ][ id ] ) ) ; dp[ h ][ pos ] = inf ; } if ( f[ h ][ id ] == u.cost + c ) { dp[ h ][ pos ] = min ( dp[ h ][ pos ] , min ( f[ h ][ 2 ] , dp[ u.vertex ][ pos ] ) ) ; } } } } void input ( ) { scanf ( "%d%d" , &n , &m ) ; scanf ( "%d%d" , &p1 , &p2 ) ; scanf ( "%d%d" , &p3 , &p4 ) ; int i ; for ( i = 1 ; i <= m ; i ++ ) { int x , y , z ; scanf ( "%d%d%d" , &x , &y , &z ) ; v[ x ].push_back ( make_pair ( y , z ) ) ; v[ y ].push_back ( make_pair ( x , z ) ) ; } inf = 1 ; for ( i = 1 ; i <= 16 ; i ++ ) { inf *= 10 ; } } void solve ( ) { dijkstra ( p3 , 1 ) ; dijkstra ( p4 , 2 ) ; calc_dp ( p1 , 3 , 1 ) ; calc_dp ( p2 , 4 , 2 ) ; int i ; long long ans = f[ p4 ][ 1 ] ; for ( i = 1 ; i <= n ; i ++ ) { if ( f[ i ][ 3 ] + f[ i ][ 4 ] == f[ p2 ][ 3 ] ) { long long cur = f[ i ][ 1 ] + min ( dp[ i ][ 1 ] , dp[ i ][ 2 ] ) ; if ( ans > cur ) { ans = cur ; } } } printf ( "%lld\n" , ans ) ; } int main ( ) { input ( ) ; solve ( ) ; return 0 ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 515 ms | 18824 KB | Output is correct |
2 | Correct | 506 ms | 18824 KB | Output is correct |
3 | Correct | 506 ms | 20004 KB | Output is correct |
4 | Correct | 535 ms | 20004 KB | Output is correct |
5 | Correct | 496 ms | 20004 KB | Output is correct |
6 | Correct | 552 ms | 20004 KB | Output is correct |
7 | Correct | 479 ms | 20004 KB | Output is correct |
8 | Correct | 519 ms | 20004 KB | Output is correct |
9 | Correct | 500 ms | 20004 KB | Output is correct |
10 | Correct | 395 ms | 20004 KB | Output is correct |
11 | Correct | 197 ms | 20004 KB | Output is correct |
12 | Correct | 518 ms | 20004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 534 ms | 20004 KB | Output is correct |
2 | Correct | 540 ms | 20004 KB | Output is correct |
3 | Correct | 529 ms | 20004 KB | Output is correct |
4 | Correct | 585 ms | 20004 KB | Output is correct |
5 | Correct | 589 ms | 20004 KB | Output is correct |
6 | Correct | 514 ms | 20004 KB | Output is correct |
7 | Correct | 551 ms | 20004 KB | Output is correct |
8 | Correct | 519 ms | 20004 KB | Output is correct |
9 | Correct | 512 ms | 20004 KB | Output is correct |
10 | Correct | 485 ms | 20004 KB | Output is correct |
11 | Correct | 209 ms | 20004 KB | Output is correct |
12 | Correct | 522 ms | 20004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 20004 KB | Output is correct |
2 | Correct | 5 ms | 20004 KB | Output is correct |
3 | Correct | 5 ms | 20004 KB | Output is correct |
4 | Correct | 28 ms | 20004 KB | Output is correct |
5 | Correct | 16 ms | 20004 KB | Output is correct |
6 | Correct | 6 ms | 20004 KB | Output is correct |
7 | Correct | 7 ms | 20004 KB | Output is correct |
8 | Correct | 8 ms | 20004 KB | Output is correct |
9 | Correct | 6 ms | 20004 KB | Output is correct |
10 | Correct | 18 ms | 20004 KB | Output is correct |
11 | Correct | 5 ms | 20004 KB | Output is correct |
12 | Correct | 6 ms | 20004 KB | Output is correct |
13 | Correct | 6 ms | 20004 KB | Output is correct |
14 | Correct | 7 ms | 20004 KB | Output is correct |
15 | Correct | 6 ms | 20004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 515 ms | 18824 KB | Output is correct |
2 | Correct | 506 ms | 18824 KB | Output is correct |
3 | Correct | 506 ms | 20004 KB | Output is correct |
4 | Correct | 535 ms | 20004 KB | Output is correct |
5 | Correct | 496 ms | 20004 KB | Output is correct |
6 | Correct | 552 ms | 20004 KB | Output is correct |
7 | Correct | 479 ms | 20004 KB | Output is correct |
8 | Correct | 519 ms | 20004 KB | Output is correct |
9 | Correct | 500 ms | 20004 KB | Output is correct |
10 | Correct | 395 ms | 20004 KB | Output is correct |
11 | Correct | 197 ms | 20004 KB | Output is correct |
12 | Correct | 518 ms | 20004 KB | Output is correct |
13 | Correct | 534 ms | 20004 KB | Output is correct |
14 | Correct | 540 ms | 20004 KB | Output is correct |
15 | Correct | 529 ms | 20004 KB | Output is correct |
16 | Correct | 585 ms | 20004 KB | Output is correct |
17 | Correct | 589 ms | 20004 KB | Output is correct |
18 | Correct | 514 ms | 20004 KB | Output is correct |
19 | Correct | 551 ms | 20004 KB | Output is correct |
20 | Correct | 519 ms | 20004 KB | Output is correct |
21 | Correct | 512 ms | 20004 KB | Output is correct |
22 | Correct | 485 ms | 20004 KB | Output is correct |
23 | Correct | 209 ms | 20004 KB | Output is correct |
24 | Correct | 522 ms | 20004 KB | Output is correct |
25 | Correct | 16 ms | 20004 KB | Output is correct |
26 | Correct | 5 ms | 20004 KB | Output is correct |
27 | Correct | 5 ms | 20004 KB | Output is correct |
28 | Correct | 28 ms | 20004 KB | Output is correct |
29 | Correct | 16 ms | 20004 KB | Output is correct |
30 | Correct | 6 ms | 20004 KB | Output is correct |
31 | Correct | 7 ms | 20004 KB | Output is correct |
32 | Correct | 8 ms | 20004 KB | Output is correct |
33 | Correct | 6 ms | 20004 KB | Output is correct |
34 | Correct | 18 ms | 20004 KB | Output is correct |
35 | Correct | 5 ms | 20004 KB | Output is correct |
36 | Correct | 6 ms | 20004 KB | Output is correct |
37 | Correct | 6 ms | 20004 KB | Output is correct |
38 | Correct | 7 ms | 20004 KB | Output is correct |
39 | Correct | 6 ms | 20004 KB | Output is correct |
40 | Correct | 485 ms | 20004 KB | Output is correct |
41 | Correct | 469 ms | 20004 KB | Output is correct |
42 | Correct | 470 ms | 20004 KB | Output is correct |
43 | Correct | 184 ms | 20004 KB | Output is correct |
44 | Correct | 137 ms | 20004 KB | Output is correct |
45 | Correct | 419 ms | 20004 KB | Output is correct |
46 | Correct | 435 ms | 20004 KB | Output is correct |
47 | Correct | 471 ms | 20004 KB | Output is correct |
48 | Correct | 227 ms | 20004 KB | Output is correct |
49 | Correct | 409 ms | 20004 KB | Output is correct |
50 | Correct | 417 ms | 20004 KB | Output is correct |
51 | Correct | 429 ms | 20004 KB | Output is correct |