#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl
using namespace std;
const long long oo = 1000000000000000000;
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen ( "sum.in", "r", stdin )
*/
int h, w, n, x[ 100001 ], y[ 100001 ], a, b, c;
vector <pair<pair<int, int>, int> > v[ 3 ][ 250001 ];
int d[ 501 ][ 501 ];
int dp[ 3 ][ 250001 ];
set <pair< int, pair<int, int> > > st;
main () {
cin >> h >> w;
cin >> a >> b >> c;
cin >> n;
for ( int i = 0; i <= h; i ++ ) {
for ( int j = 0; j <= w; j ++ )
d[ i ][ j ] = oo;
}
for ( int i = 1; i <= n; i ++ ) {
cin >> x[ i ] >> y[ i ];
for ( int j = 0; j <= h; j ++ ) {
d[ j ][ y[ i ] ] = min( d[ j ][ y[ i ] ], abs( x[ i ] - j ) );
}
for ( int j = 0; j <= w; j ++ )
d[ x[ i ] ][ j ] = min( d[ x[ i ] ][ j ], abs( j - y[ i ] ) );
}
for ( int i = 0; i <= h; i ++ ) {
for ( int j = 0; j <= w; j ++ ) {
for ( int k = 0; k <= h; k ++ )
d[ i ][ j ] = min( d[ i ][ j ], d[ k ][ j ] + abs( k - i ) );
for ( int k = 1; k <= w; k ++ )
d[ i ][ j ] = min( d[ i ][ j ], d[ i ][ k ] + abs( k - j ) );
}
}
for ( int i = 0; i <= h; i ++ ) {
for ( int j = 0; j <= w; j ++ ) {
num = ( i ) * ( w + 1 ) + j;
v[ 0 ][ num ].push_back( { make_pair( 1, num ), b } );
v[ 0 ][ num ].push_back( { make_pair( 2, num ), b } );
v[ 1 ][ num ].push_back( { make_pair( 0, num ), d[ i ][ j ] * c } );
v[ 2 ][ num ].push_back( { make_pair( 0, num ), d[ i ][ j ] * c } );
if ( i ) {
v[ 0 ][ num ].push_back( { make_pair( 0, num - w - 1 ), c } );
v[ 1 ][ num ].push_back( { make_pair( 1, num - w - 1 ), a } );
}
if ( i < h ) {
v[ 0 ][ num ].push_back( { make_pair( 0, num + w + 1 ), c } );
v[ 1 ][ num ].push_back( { make_pair( 1, num + w + 1 ), a } );
}
if ( j ) {
v[ 0 ][ num ].push_back( { make_pair( 0, num - 1 ), c } );
v[ 2 ][ num ].push_back( { make_pair( 2, num - 1 ), a } );
}
if ( j < w ) {
v[ 0 ][ num ].push_back( { make_pair( 0, num + 1 ), c } );
v[ 2 ][ num ].push_back( { make_pair( 2, num + 1 ), a } );
}
}
}
for ( int i = 0; i <= ( h + 1 ) * ( w + 1 ); i ++ )
for ( int j = 0; j < 3; j ++ )
dp[ j ][ i ] = oo;
dp[ 0 ][ x[ 1 ] * ( w + 1 ) + y[ 1 ] ] = 0;
st.insert( { 0, make_pair( 0, x[ 1 ] * ( w + 1 ) + y[ 1 ] ) } );
while ( st.size() ) {
pair<int, int> p = st.begin()->second;
st.erase( st.begin() );
for ( auto to : v[ p.first ][ p.second ] ) {
if ( dp[ to.first.first ][ to.first.second ] > dp[ p.first ][ p.second ] + to.second ) {
st.erase( { dp[ to.first.first ][ to.first.second ], to.first } );
dp[ to.first.first ][ to.first.second ] = dp[ p.first ][ p.second ] + to.second;
st.insert( { dp[ to.first.first ][ to.first.second ], to.first } );
}
}
}
cout << dp[ 0 ][ x[ n ] * ( w + 1 ) + y[ n ] ];
}
/*
1 - kick x
2 - kick y
0 - go
*/
Compilation message
soccer.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
54 | main () {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
164 ms |
48268 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18016 KB |
Output is correct |
| 3 |
Runtime error |
568 ms |
254156 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
600 ms |
254236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
164 ms |
48268 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18016 KB |
Output is correct |
| 3 |
Runtime error |
568 ms |
254156 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
