C++14(g++5.4) 解法, 执行用时: 267ms, 内存消耗: 2836K, 提交时间: 2020-09-23 09:14:23

#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());
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 306ms, 内存消耗: 1112K, 提交时间: 2020-05-24 16:26:59

#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));
	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());
	}
}