| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 83824 |
2018-11-11T06:57:34 Z |
ekrem |
Soccer (JOI17_soccer) |
C++ |
|
295 ms |
32840 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000000000000007
#define ek(a,b,c,d,e) mp(a,mp(mp(b,c),mp(d,e)))
#define N 505
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
typedef pair < ii , ii > i4;
int n, m, k, x[N*N], y[N*N];
ll a, b, c, ans = inf, d[N][N][4][4];
int o[] = {0, 0, 1, -1};
int p[] = {1, -1, 0, 0};
priority_queue < pair < ll , i4 > > q;
bool git(int i, int j){return !(i < 1 or j < 1 or i > n or j > m);}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
memset(d, 60, sizeof d);
scanf("%d %d %lld %lld %lld %d",&n ,&m ,&a ,&b ,&c ,&k);n++;m++;
scanf("%d %d",x + 1, y + 1);x[1]++;y[1]++;
d[x[1]][y[1]][3][0] = 0;
q.push(ek(0, x[1], y[1], 3, 0));
for(int i = 2; i <= k; i++){
scanf("%d %d",x + i, y + i);x[i]++;y[i]++;
d[x[i]][y[i]][2][0] = 0;
q.push(ek(0, x[i], y[i], 2, 0));
}
while(!q.empty()){
pair < ll , i4 > tp = q.top();q.pop();
int x = tp.nd.st.st, y = tp.nd.st.nd, dur = tp.nd.nd.st, yon = tp.nd.nd.nd;
if(dur == 0){
if(d[x][y][1][0] > d[x][y][0][yon]){//Topu durdur.
d[x][y][1][0] = d[x][y][0][yon];
q.push(ek(-d[x][y][1][0], x, y, 1, 0));
}
if(git(x + o[yon], y + p[yon]) and d[x + o[yon]][y + p[yon]][0][yon] > d[x][y][0][yon] + a){
d[x + o[yon]][y + p[yon]][0][yon] = d[x][y][0][yon] + a;
q.push(ek(-d[x + o[yon]][y + p[yon]][0][yon], x + o[yon], y + p[yon], 0, yon));
}
}
if(dur == 1){
if(d[x][y][3][0] > d[x][y][1][0] + d[x][y][2][0]){
d[x][y][3][0] = d[x][y][1][0] + d[x][y][2][0];
q.push(ek(-d[x][y][3][0], x, y, 3, 0));
}
}
if(dur == 2){
if(d[x][y][3][0] > d[x][y][1][0] + d[x][y][2][0]){
d[x][y][3][0] = d[x][y][1][0] + d[x][y][2][0];
q.push(ek(-d[x][y][3][0], x, y, 3, 0));
}
for(int i = 0; i < 4; i++){
if(git(x + o[i], y + p[i]) and d[x + o[i]][y + p[i]][2][0] > d[x][y][2][0] + c){
d[x + o[i]][y + p[i]][2][0] = d[x][y][2][0] + c;
q.push(ek(-d[x + o[yon]][y + p[yon]][2][0], x + o[yon], y + p[yon], 2, 0));
}
}
}
if(dur == 3){
for(int i = 0; i < 4; i++){
if(git(x + o[i], y + p[i]) and d[x + o[i]][y + p[i]][3][0] > d[x][y][3][0] + c){
d[x + o[i]][y + p[i]][3][0] = d[x][y][3][0] + c;
q.push(ek(-d[x + o[yon]][y + p[yon]][3][0], x + o[yon], y + p[yon], 3, 0));
}
}
for(int i = 0; i < 4; i++){
if(d[x][y][0][i] > d[x][y][3][0] + b){
d[x][y][0][i] = d[x][y][3][0] + b;
q.push(ek(-d[x][y][0][i], x, y, 0, i));
}
}
if(d[x][y][1][0] > d[x][y][3][0]){
d[x][y][1][0] = d[x][y][3][0];
q.push(ek(-d[x][y][1][0], x, y, 1, 0));
}
if(d[x][y][2][0] > d[x][y][3][0]){
d[x][y][2][0] = d[x][y][3][0];
q.push(ek(-d[x][y][2][0], x, y, 2, 0));
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ans = min(ans, abs(x[k] - i)*c + abs(y[k] - j)*c + d[i][j][1][0]);
printf("%lld\n", ans);
return 0;
}
Compilation message
soccer.cpp: In function 'int main()':
soccer.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld %lld %lld %d",&n ,&m ,&a ,&b ,&c ,&k);n++;m++;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",x + 1, y + 1);x[1]++;y[1]++;
~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",x + i, y + i);x[i]++;y[i]++;
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
32324 KB |
Output is correct |
| 2 |
Correct |
36 ms |
32380 KB |
Output is correct |
| 3 |
Correct |
86 ms |
32432 KB |
Output is correct |
| 4 |
Correct |
95 ms |
32524 KB |
Output is correct |
| 5 |
Correct |
50 ms |
32524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
295 ms |
32840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
32324 KB |
Output is correct |
| 2 |
Correct |
36 ms |
32380 KB |
Output is correct |
| 3 |
Correct |
86 ms |
32432 KB |
Output is correct |
| 4 |
Correct |
95 ms |
32524 KB |
Output is correct |
| 5 |
Correct |
50 ms |
32524 KB |
Output is correct |
| 6 |
Incorrect |
295 ms |
32840 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
