牛客练习赛64 E-红色的樱花

题目传送门

题目大意： 有一张 的网格图，起点为 ，终点为 ，有三种移动方式：1、 选择一个 ，移动到 ，代价为 ；2、移动到 ，代价为 ；3、移动到 ，代价为 ，问能否到达终点，能的话最小代价是多少。

题解

比较显然的是操作 至多用一次，那么看一下用和不用哪个代价更小即可。

假如只看操作 ，那么从 出发能走到 ，最后走回 。这样的路径我们称之为一个循环，那么一个循环的长度就是 ，一共有 个循环。

假如 和 在同一个循环内，那么直接一次操作 就可以了，假如不在的话，就需要用操作 来跳到同一个循环内。

但是可以发现，只用其中一个操作是最优的，不需要同时用到两个操作，因为两个操作同时用的话，相当于从 到 ，这等价于让操作 的 加 ，而这样还能让费用减少 。

那么接下来就是考虑求出从 到 所在循环需要多少代价了，假如只用操作 ，即只更改 坐标，那么就是求出这个方程的解：，转化一下就是 ，扩欧即可。

只用操作 也是类似的，。

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
#define inf 999999999999999999ll

ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)return x=1,y=0,a;
    ll d=exgcd(b,a%b,y,x);
    return y-=a/b*x,d;
}
ll getans(ll a,ll b,ll c,ll cost)
{
    ll x,y,GCD=exgcd(a,b,x,y);
    if(c%GCD)return inf;
    b/=GCD;if(b<0)b=-b;
    return (c/GCD*x%b+b)%b*cost;
}
ll T,n,m,d,sx,sy,ex,ey,a,b,c;
ll solve()
{
    if(sx==ex&&sy==ey)return 0;
    ll re=min(inf,getans(d,n,(ex-sx+n)%n,b)+getans(d,m,(ey-sy+m)%m,c));//不用操作1
    ll GCD=gcd(n,m);
    re=min(re,getans(d,GCD,((ex-sx+GCD)%GCD-(ey-sy+GCD)%GCD+GCD)%GCD,b)+a);
    re=min(re,getans(d,GCD,((ey-sy+GCD)%GCD-(ex-sx+GCD)%GCD+GCD)%GCD,c)+a);
    return re==inf?-1:re;
}

int main()
{
    scanf("%d",&T);while(T--)
    {
        scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld %lld",&n,&m,&d,&sx,&sy,&ex,&ey,&a,&b,&c);
        printf("%lld\n",solve());
    }
}