#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
#define PII pair<pii,pii>
using namespace std;
const int N = 505 + 5, inf = 1e18; // !
int d[N][N][2], D[N][N][6];int n, m;
int dx[] = {0, 0, 0, 1, -1}, dy[] = {0, 1, -1, 0, 0};
bool ok(int i,int j) {
return (min(i, j) >= 0 && i <= n && j <= m);
}
main(){
cin >> n >> m;
int a, b, c;
cin >> a >> b >> c;
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
d[i][j][0] = d[i][j][1] = inf;
for(int t = 0; t <= 5; ++t) D[i][j][t] = inf;
}
}
int Q;
cin >> Q;
priority_queue<PII, vector<PII>, greater<PII> > pq;
queue<pair<int,int>> q[2];
for(int i = 1; i <= Q; i++) {
int x, y; cin >> x >> y;
if(d[x][y][0])
q[0].push({x, y});
d[x][y][0] = 0;
if(i == 1) {
D[x][y][0] = 0;
pq.push({{0, 0}, {x, y}});
}
if(i == Q) {
d[x][y][1] = 0;
q[1].push({x, y});
}
}
for(int t = 0; t < 2; t++)
while(q[t].size()) {
int x = q[t].front().f, y = q[t].front().s;
q[t].pop();
for(int j = 1; j <= 4; j++) {
int xn = x + dx[j], yn = y + dy[j];
if(ok(xn, yn) && d[xn][yn][t] > d[x][y][t] + c) {
d[xn][yn][t] = d[x][y][t] + c;
q[t].push({xn, yn});
}
}
}
int ans = 1e18;
while(pq.size()) {
int di = pq.top().f.f, t = pq.top().f.s;
int x = pq.top().s.f, y = pq.top().s.s;
pq.pop();
if(D[x][y][t] < di) continue;
ans = min(ans, D[x][y][t] + d[x][y][1]);
if(t && t < 5) {
int xn = x +dx[t], yn = y + dy[t];
if(D[xn][yn][t] > di + a) {
D[xn][yn][t] = di + a;
pq.push({{di + a, t}, {xn, yn}});
}
if(D[x][y][5] > di) {
D[x][y][5] = di;
pq.push({{di, 5}, {x, y}});
}
continue;
}
if(t == 5) {
if(D[x][y][0] > D[x][y][5] + d[x][y][0]) {
D[x][y][0] = D[x][y][5] + d[x][y][0];
pq.push({{D[x][y][0], 0}, {x, y}});
}
continue;
}
for(int t = 1; t < 5; t++) {
int xn = x + dx[t], yn = y + dy[t];
if(!ok(xn, yn)) continue;
if(D[xn][yn][0] > di + c) {
D[xn][yn][0] = di + c;
pq.push({{di + c, 0}, {xn, yn}});
}
if(D[xn][yn][t] > di + a + b) {
D[xn][yn][t] = di + a + b;
pq.push({{di + a + b, t}, {xn, yn}});
}
}
}
cout << ans;
}
Compilation message
soccer.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
14 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
13648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
79 ms |
39392 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
13648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
