This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define endl "\n"
const ll inf = 1e18;
const int N = 505;
int dx[] = {-1, 0,1,0};
int dy[] = { 0,-1,0,1};
typedef pair<ll,int> ii;
vector<ii> g[N];
int d[N][N];
int S, T;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int H, W; cin >> H >> W;
int A, B; cin >> A >> B;
int C; cin >> C;
H++;
W++;
for(int i = 0 ; i < H ; ++i)
for(int j = 0 ; j < W ; ++j)
d[i][j] = -1;
int n; cin >> n;
queue<ii> qu;
for(int i = 0 ; i < n ; ++i) {
int x; cin >> x;
int y; cin >> y;
d[x][y] = 0;
qu.push(ii(x,y));
if (i == 0) S = (x * W + y) * 5 + 4;
if (i == n - 1) T = (x * W + y) * 5 + 4;
}
while (qu.size()) {
int x = qu.front().X;
int y = qu.front().Y; qu.pop();
for(int i = 0 ; i < 4 ; ++i) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx >= H) continue;
if (yy < 0 || yy >= W) continue;
if (d[xx][yy] < 0) {
d[xx][yy] = d[x][y] + 1;
qu.push(ii(xx,yy));
}
}
}
for(int i = 0 ; i < H ; ++i)
for(int j = 0 ; j < W ; ++j)
for(int k = 0 ; k < 4 ; ++k) {
int x = i + dx[k];
int y = j + dy[k];
int u = (i * W + j) * 5;
int v = (x * W + y) * 5;
g[u + k].pb(1ll * C * d[i][j] + B,u + 4);
if (x < 0 || x >= H) continue;
if (y < 0 || y >= W) continue;
g[u + 4].pb(C,v + 4);
g[u + k].pb(A,v + k);
g[u + 4].pb(A,v + k);
}
vector<ll> dis(H * W * 5 + 5,inf);
priority_queue<ii,vector<ii>,greater<ii> > pq;
pq.push(ii(0,S)); dis[S] = 0;
while (pq.size()) {
int u = pq.top().Y;
ll du = pq.top().X;
pq.pop();
if (du != dis[u])
continue;
for(ii e : g[u]) {
int v = e.Y;
ll C = e.X;
if (dis[v] > du + C) {
dis[v] = du + C;
pq.push(ii(dis[v],v));
}
}
}
cout << dis[T] << endl;
}
/*
6 5
1 3 6
3
1 1
0 4
6 5
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |