I wonder in this problem why each time we reach a field we only need to update the time distance 3 steps and 1 step ahead as the official solution in USACO Guide said. I also keep track of 2 steps but it got me wrong answer (pass only test case 1, 10, and 11). I’d appreciate if someone could explain to me. Thank you
USACO
Solution
Here is my code:
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x, y;
long long dist;
bool operator<(const node &b) const
{
return b.dist <= dist;
}
};
typedef pair<int, int> ii;
const int MAX_N = 100;
int dx[24] = {-3, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3};
int dy[24] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -3, -2, -1, 1, 2, 3, -2, -1, 0, 1, 2, -1, 0, 1, 0};
long long n, k;
long long a[MAX_N][MAX_N];
long long d[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];
long long dijkstra(int si, int sj, int fi, int fj)
{
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) d[i][j] = LLONG_MAX;
d[si][sj] = 0;
priority_queue<node, vector<node> > pq;
pq.push({si, sj, 0});
while(!pq.empty()){
int ui = pq.top().x, uj = pq.top().y;
long long t = pq.top().dist;
pq.pop();
if(vis[ui][uj]) continue;
vis[ui][uj] = true;
for(int i = 0; i < 24; i++){
int vi = ui + dx[i], vj = uj + dy[i];
if(vi >= n || vi < 0 || vj >= n || vj < 0) continue;
long long w = 3 * k + a[vi][vj];
if(d[vi][vj] > d[ui][uj] + w){
d[vi][vj] = d[ui][uj] + w;
pq.push({vi, vj, d[vi][vj]});
}
}
long long about = abs(fi - ui) + abs(fj - uj);
if(about < 3)
if(t + about * k < d[fi][fj]){
d[fi][fj] = t + about * k;
}
}
return d[fi][fj];
}
int main()
{
freopen("visitfj.in","r",stdin);
freopen("visitfj.out","w",stdout);
cin>>n>>k;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin>>a[i][j];
}
}
cout<<dijkstra(0, 0, n - 1, n - 1);
return 0;
}