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;
}