제출 #33339

#제출 시각아이디문제언어결과실행 시간메모리
33339ngkan146Soccer (JOI17_soccer)C++98
0 / 100
3000 ms22856 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; typedef pair<ll,int> ii; #define fi first #define se second int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; ll A,B,C; int n,h,w; ll dp0[505][505], dp1[505][505][4]; bool player[505][505]; int min_distance[505][505]; void prep(){ queue <int> q; for(int i=0;i<=h;i++) for(int j=0;j<=w;j++){ if (player[i][j]) min_distance[i][j] = 0, q.push(i * 501 + j); else min_distance[i][j] = 100000; } while(q.size()){ int x = q.front() / 501; int y = q.front() % 501; q.pop(); for(int k=0;k<4;k++){ int X = x + dx[k]; int Y = y + dy[k]; if (0 > X || X > h || 0 > Y || Y > w) continue; if (min_distance[X][Y] > min_distance[x][y] + 1) min_distance[X][Y] = min_distance[x][y] + 1, q.push(X * 501 + Y); } } } #define x1 asd #define y1 jnda #define xn addaf #define yn nln int x1,y1,xn,yn; void prep_dp(){ for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) dp0[i][j] = dp1[i][j][0] = dp1[i][j][1] = dp1[i][j][2] = dp1[i][j][3] = (ll) 1e18; dp0[x1][y1] = 0; } bool visited[5][505][505]; void cal_dp(){ for(int _time=0;_time<=500;_time++){ priority_queue <ii,vector<ii>,greater<ii> > pq; for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) pq.push(ii(dp0[i][j], i*3500 + j * 5 + 0)); while(pq.size()){ int x = pq.top().se / 3500; int y = (pq.top().se % 3500) / 5; int type = pq.top().se % 5; pq.pop(); if (visited[type][x][y]) continue; visited[type][x][y] = 1; if (type == 0){ for(int k=0;k<4;k++){ int X = x + dx[k]; int Y = y + dy[k]; if (0 > X || X > h || 0 > Y || Y > w) continue; if (dp1[X][Y][k] > dp0[x][y] + A + B) dp1[X][Y][k] = dp0[x][y] + A + B, pq.push(ii(dp1[X][Y][k], X * 3500 + Y * 5 + k+1)); if (dp0[X][Y] > dp0[x][y] + C) dp0[X][Y] = dp0[x][y] + C, pq.push(ii(dp0[X][Y], X * 3500 + Y * 5 + k+1)); } } else{ int X = x + dx[type-1]; int Y = y + dy[type-1]; if (0 > X || X > h || 0 > Y || Y > w) continue; if (dp1[X][Y][type-1] > dp1[x][y][type-1] + A) dp1[X][Y][type-1] = dp1[x][y][type-1] + A, pq.push(ii(dp1[X][Y][type-1], X * 3500 + Y * 5 + type)); } } for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) for(int t=0;t<4;t++) dp0[i][j] = min(dp0[i][j], dp1[i][j][t] + min_distance[i][j] * C), dp1[i][j][t] = (ll) 1e18; memset(visited,0,sizeof(visited)); //for(int i=0;i<=h;i++){ // for(int j=0;j<=w;j++){ // if (dp0[i][j] != (ll) 1e18) cout << dp0[i][j] << ' '; // else cout << -1; // } // cout << endl; //} //cout << endl; } } int main(){ iostream::sync_with_stdio(0); cin >> h >> w; cin >> A >> B >> C; cin >> n; for(int i=1;i<=n;i++){ int x,y; cin >> x >> y; if (i == 1) x1 = x, y1 = y; if (i == n) xn = x, yn = y; player[x][y] = 1; } prep(); prep_dp(); cal_dp(); cout << dp0[xn][yn]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...