本文主要是介绍Codeforces Round 927 G. Moving Platforms，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：Problem - G - Codeforces
题目大意：有n个平台，m个通道，n个平台高度不一定相同，只有高度相同的时候才可以通过通道去下一个平台，通过通道时间为1秒，平台的高度每一秒都会增加，但是不会超过最高高度H，如果超过会立刻变为1，例如最高高度为10，一个平台高度为8，一秒它会上升5，因为会超过10，所以一秒过后它的高度会变成3，也就是(8+5)%10,问从第一块平台最短时间走到最后一块平台？无法到达输出-1。
思路：由题意可知，如果二个平台高度不相同，那么可以在当前平台等待目标平台和当前平台平行再走，那么如何快速的算出当前平台和目标平台相同高度需要经过的时间？可以想到使用拓展欧几米德算法，u为当前平台，v为目标平台，Lu为当前u平台高度，Su为u平台每秒变化的高度。根据题意可以得到Lu+x*Su+y*H=Lv+x*Sv => x*(Su-Sv)+y*H=Lv-Lu，这就是不定方程的形式，根据拓展欧几米德算法就可以得到从当前平台和目标平台平行的最短时间。那么剩下的就可以通过跑迪杰斯特拉算法来求最短路了。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1e9+7;
ll h[N],e[N],ne[N],idx,d[N],l[N],s[N];
bool st[N];
void add(ll a,ll b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(b==0){x=1,y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
int main()
{ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){ll n,m,H;cin>>n>>m>>H;idx=0;for(int i=1;i<=n;i++){cin>>l[i];d[i]=1e18;h[i]=-1;st[i]=0;}for(int i=1;i<=n;i++){cin>>s[i];}while(m--){ll a,b;cin>>a>>b;add(a,b);add(b,a);}priority_queue<pii,vector<pii>,greater<pii>> op;d[1]=0;op.push({d[1],1});while(op.size()){auto v=op.top();op.pop();if(st[v.second])continue;st[v.second]=1;for(ll i=h[v.second];~i;i=ne[i]){ll j=e[i];ll x,y,a=s[v.second]-s[j],b=H,c=l[j]-l[v.second];ll g=exgcd(a,b,x,y);//根据拓展欧几米德算法，求出ax+by=gcd(a,b)中的gcd(a,b)和一组x，y。 if(c%g!=0)continue;//如果c不是gcd(a,b)的倍数代表从当前平台无法到目标平台 x=x*c/g;//求出ax+by=c的x ll dx=abs(b/g);ll k=ceil((1.0*v.first-x)/dx);//下一次二个平台高度相同发生的时间必须大于在当前平台的时间 x=x+k*dx; if(d[j]>x+1){d[j]=x+1;op.push({d[j],j});}}}if(d[n]>=1e18)cout<<-1<<endl;else cout<<d[n]<<endl;}return 0;
}这篇关于Codeforces Round 927 G. Moving Platforms的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
