#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
long long di[] = {0 , 0 , 0 , 1 , -1};
long long dj[] = {0 , 1 , -1 , 0 , 0};
priority_queue <pair <pair <long long,long long> , pair <long long,long long> > > h;
pair <long long,long long> v[100010];
deque <pair <long long,long long> > dq;
long long f[510][510];
long long dp[510][510][6];
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
long long n , m , a , b , c , k , ic , jc , iv , jv , dirc , dirv , i , j , val , d;
fscanf (fin,"%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&k);
n++;
m++;
for (i = 1 ; i <= k ; i++){
fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
v[i].first++;
v[i].second++;
if (i != k){ /// modifica aici daca vrei sa se plimbe si k
dq.push_back(v[i]);
f[v[i].first][v[i].second] = 1;
}
}
while (!dq.empty()){
ic = dq.front().first;
jc = dq.front().second;
dq.pop_front();
for (d = 1 ; d <= 4 ; d++){
iv = ic + di[d];
jv = jc + dj[d];
if (iv > 0 && jv > 0 && iv <= n && jv <= m && !f[iv][jv]){
f[iv][jv] = 1 + f[ic][jc];
dq.push_back(make_pair(iv , jv));
}
}
}
/// f[i][j] - 1 = distanta minima de la orice jucator (in afr de k) la i j
/// dp[i][j][dir] = cost minim sa ajungi in i j si directia sa fie dir
/// dir = 0 => apartine unui jucator
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j <= m ; j++){
for (d = 0 ; d < 5 ; d++)
dp[i][j][d] = INF;
}
}
dp[v[1].first][v[1].second][0] = 0; /// stare initiala
h.push(make_pair( make_pair(0 , 0) , v[1] ) );
while (!h.empty()){
val = -h.top().first.first;
dirc = h.top().first.second;
ic = h.top().second.first;
jc = h.top().second.second;
h.pop();
//if (ic == 2 && jc == 5 && dirc == 1)
// printf ("a");
if (dp[ic][jc][dirc] != val)
continue;
//printf ("%lld %lld %lld\n" , ic , jc , dirc);
if (ic == v[k].first && jc == v[k].second){
fprintf (fout,"%lld",val);
return 0;
}
if (dirc != 0){ /// nu apartine niciunui jucator si e intr un sut
/// cazul 1 : un jucator o sa vina sa o ia aici
dirv = 0;
iv = ic;
jv = jc;
if (dp[iv][jv][dirv] > dp[ic][jc][dirc] + c * ( f[iv][jv] - 1 ) ){
dp[iv][jv][dirv] = dp[ic][jc][dirc] + c * ( f[iv][jv] - 1 );
h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
}
/// cazul 2 : continua pe directia aia
dirv = dirc;
iv = ic + di[dirc];
jv = jc + dj[dirc];
if (iv > 0 && jv > 0 && iv <= n && jv <= m && dp[iv][jv][dirv] > dp[ic][jc][dirc] + a ){
dp[iv][jv][dirv] = dp[ic][jc][dirc] + a;
h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
}
}
else {
/// acum apartine unui jucator
/// cazul 1 : jucatorul asta face un pas cu ea
dirv = 0;
for (d = 1 ; d < 5 ; d++){
iv = ic + di[d];
jv = jc + dj[d];
if (iv > 0 && jv > 0 && iv <= n && jv <= m && dp[iv][jv][dirv] > dp[ic][jc][dirc] + c ){
dp[iv][jv][dirv] = dp[ic][jc][dirc] + c;
h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
}
}
/// cazul 2 : jucatorul care o are acum ii da un sut intr o directie
for (d = 1 ; d < 5 ; d++){
iv = ic + di[d];
jv = jc + dj[d];
dirv = d;
if (iv > 0 && jv > 0 && iv <= n && jv <= m && dp[iv][jv][dirv] > dp[ic][jc][dirc] + a + b ){
dp[iv][jv][dirv] = dp[ic][jc][dirc] + a + b;
h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
}
}
}
}
return 0;
}
Compilation message
soccer.cpp: In function 'int main()':
soccer.cpp:16:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&k);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:20:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
7796 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
14336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
7796 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
14336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
