제출 #717983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717983		vinnipuh01	Soccer (JOI17_soccer)	C++17	100 / 100	1167 ms	147408 KiB

soccer

#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 ][ 501 * 501 + 1 ];
int d[ 502 ][ 502 ];
int dp[ 3 ][ 501 * 501 ];
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

*/

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main () {
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65