| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 670564 |
2022-12-09T14:31:03 Z |
S2speed |
Soccer (JOI17_soccer) |
C++17 |
|
231 ms |
262144 KB |
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<pll , ll> plll;
typedef pair<ll , plll> pllll;
const ll maxn = 502 , inf = 2e18;
ll n , m , A , B , C;
ll dis[maxn][maxn][5];
short int f[maxn][maxn];
vector<pll> bfs;
priority_queue<pllll , vector<pllll> , greater<pllll>> pq;
void BFS(){
ll x = 0;
while(x < sze(bfs)){
ll i = bfs[x].first , j = bfs[x++].second;
if(i > 0){
if(f[i - 1][j] > f[i][j]){
f[i - 1][j] = f[i][j] + 1;
bfs.push_back({i - 1 , j});
}
}
if(j > 0){
if(f[i][j - 1] > f[i][j]){
f[i][j - 1] = f[i][j] + 1;
bfs.push_back({i , j - 1});
}
}
if(i < n){
if(f[i + 1][j] > f[i][j]){
f[i + 1][j] = f[i][j] + 1;
bfs.push_back({i + 1 , j});
}
}
if(j < m){
if(f[i][j + 1] > f[i][j]){
f[i][j + 1] = f[i][j] + 1;
bfs.push_back({i , j + 1});
}
}
}
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(f , 63 , sizeof(f));
memset(dis , 63 , sizeof(dis));
ll k , x , y;
cin>>n>>m>>A>>B>>C>>k;
for(ll i = 0 ; i < k ; i++){
cin>>x>>y;
if(i == 0){
dis[x][y][0] = 0;
pq.push({0 , {{x , y} , 0}});
}
if(f[x][y] > 0) bfs.push_back({x , y});
f[x][y] = 0;
}
BFS();
while(!pq.empty()){
pllll p = pq.top(); pq.pop();
ll i = p.second.first.first , j = p.second.first.second , t = p.second.second;
if(dis[i][j][t] != p.first) continue;
if(t == 0){
ll ps = dis[i][j][0] + B;
if(dis[i][j][1] > ps){
dis[i][j][1] = ps;
pq.push({ps , {{i , j} , 1}});
}
if(dis[i][j][2] > ps){
dis[i][j][2] = ps;
pq.push({ps , {{i , j} , 2}});
}
if(dis[i][j][3] > ps){
dis[i][j][3] = ps;
pq.push({ps , {{i , j} , 3}});
}
if(dis[i][j][4] > ps){
dis[i][j][4] = ps;
pq.push({ps , {{i , j} , 4}});
}
ll dr = dis[i][j][0] + C;
if(i > 0){
if(dis[i - 1][j][0] > dr){
dis[i - 1][j][0] = dr;
pq.push({dr , {{i - 1 , j} , 0}});
}
}
if(j > 0){
if(dis[i][j - 1][0] > dr){
dis[i][j - 1][0] = dr;
pq.push({dr , {{i , j - 1} , 0}});
}
}
if(i < n){
if(dis[i + 1][j][0] > dr){
dis[i + 1][j][0] = dr;
pq.push({dr , {{i + 1 , j} , 0}});
}
}
if(j < m){
if(dis[i][j + 1][0] > dr){
dis[i][j + 1][0] = dr;
pq.push({dr , {{i , j + 1} , 0}});
}
}
} else {
ll rc = dis[i][j][t] + f[i][j] * C;
if(dis[i][j][0] > rc){
dis[i][j][0] = rc;
pq.push({rc , {{i , j} , 0}});
}
}
if(t == 1){
ll ps = dis[i][j][1] + A;
if(i > 0){
if(dis[i - 1][j][1] > ps){
dis[i - 1][j][1] = ps;
pq.push({ps , {{i - 1 , j} , 1}});
}
}
} else if(t == 2){
ll ps = dis[i][j][2] + A;
if(i < n){
if(dis[i + 1][j][2] > ps){
dis[i + 1][j][2] = ps;
pq.push({ps , {{i + 1 , j} , 2}});
}
}
} else if(t == 3){
ll ps = dis[i][j][3] + A;
if(j > 0){
if(dis[i][j - 1][3] > ps){
dis[i][j - 1][3] = ps;
pq.push({ps , {{i , j - 1} , 3}});
}
}
} else if(t == 4){
ll ps = dis[i][j][4] + A;
if(j < m){
if(dis[i][j + 1][4] > ps){
dis[i][j + 1][4] = ps;
pq.push({ps , {{i , j + 1} , 4}});
}
}
}
}
ll ans = inf;
for(ll j = 0 ; j < 5 ; j++) ans = min(ans , dis[x][y][j]);
cout<<ans<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
231 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
