Problem

你位于$(0,-1)$到$(0,0)$的路上,每到一个整点,你可以选择左右转或者直行,右转不产生代价,左转的代价为$a$,直行的代价为$b$,求抵达目标点$(x,y)$的最小代价

Solution

考虑到右转不花费代价,我们将每四条边缩点,以方格中心为点重构图

在新图中,直行代价为$b$,斜行代价为$a$,先求出通过斜行或者直行走到一条直线上的最小代价,然后求解一条直线的最小代价即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a, b;
ll Calc(ll x, ll y) {
if (y < x) swap(x, y);
ll res = x * min(a, 2 * b);
y -= x;
res += (y / 2) * 2 * min(a, b);
if (y & 1) res += b;
return res;
}
int T, x, y;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d", &a, &b, &x, &y);
ll ans = Calc(abs(x), abs(y));
ans = min(ans, Calc(abs(x - 1), abs(y + 1)));
ans = min(ans, Calc(abs(x - 1), abs(y)));
ans = min(ans, Calc(abs(x), abs(y + 1)));
printf("%lld\n", ans);
}
return 0;
}