牛客练习赛64 E-红色的樱花
红色的樱花
https://ac.nowcoder.com/acm/contest/5633/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()); } }