Autobus 方法记录( 三 ) _生活百科

b[i][j]=minn(b[i][j],a[i][l]+init[l][j]);这就是核心转移方程，其中\(b\)数组记录下一次的答案，\(a\)数组记录这一次的答案，\(init\)数组是我们最开始输入的图，它正代表着“新的选择” 。
为了维护这个转移方程，首先我们要把输入的图记录下来——\(init\)数组在后续是不会改变的；然后用\(a,b\)两个数组记录这次的结果和下次的结果。具体地讲，就是每轮循环开始时将\(a\)赋给\(b\)，跑完\(floyd\)后再将\(b\)赋给\(a\)，如此往复。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=75;const int inf=1e9;int n,m,u,v,t;int k,q,c,d;int init[N][N],a[N][N],b[N][N];int minn(int a,int b){ return a<b?a:b;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)init[i][j]=inf;//init数组初始化为一个极大值 for(int i=1;i<=n;i++)init[i][i]=0; for(int i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&t);init[u][v]=minn(init[u][v],t); } scanf("%d%d",&k,&q); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=init[i][j];//a数组最开始的状态就是init k=minn(k,n);//同理，每个点最多到一次，所以和n取最小 for(int p=2;p<=k;p++) {for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=a[i][j];//a赋给bfor(int l=1;l<=n;l++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=minn(b[i][j],a[i][l]+init[l][j]);//核心：floydfor(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=b[i][j];//b赋给a } for(int i=1;i<=q;i++) {scanf("%d%d",&c,&d);if(c==d) puts("0");else if(a[c][d]==inf) puts("-1");else printf("%d\n",a[c][d]); } return 0;}还可以更快吗？注意到转移方程:
b[i][j]=minn(b[i][j],a[i][l]+init[l][j]);因为该转移满足结合律，所以考虑用广义矩阵快速幂优化。再想，上个方法的最外层循环是不是在枚举\(k\)？那么，这个转移从本质上来讲就是求\(init[l][j]^k\).
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N=75;const int inf=0x3f3f3f3f;//为了方便memset的使用，inf不可以开成1e9int n,m,u,v,t;int x,q,c,d;int init[N][N];int ans[N][N];int minn(int x,int y){ return x<y?x:y;}void mul(int a[N][N],int b[N][N])//矩阵乘法，仔细观察会发现转移方程像极了floyd{ int c[N][N]; memset(c,inf,sizeof(c)); for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=minn(c[i][j],a[i][k]+b[k][j]); memcpy(a,c,sizeof(c));}int main(){ scanf("%d%d",&n,&m); memset(init,inf,sizeof(init)); for(int i=1;i<=n;i++) init[i][i]=0; for(int i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&t);init[u][v]=minn(init[u][v],t); } scanf("%d%d",&x,&q); x=minn(x,n); memset(ans,inf,sizeof(ans)); for(int i=1;i<=n;i++) ans[i][i]=0; while(x)//矩阵快速幂 {if(x&1) mul(ans,init);mul(init,init);x>>=1; } for(int i=1;i<=q;i++) {scanf("%d%d",&c,&d);if(ans[c][d]==inf) puts("-1");else printf("%d\n",ans[c][d]); } return 0;}【Autobus 方法记录】

Autobus 方法记录( 三 )

经验总结扩展阅读

玉和翡翠假的怎么分辨

智商|“以油养肤”是在交智商税？最全网红护肤油测评，拿走不谢！

美白的真谛是什么

墨鱼自蔽和什么寓言故事类似

多人运动事件是什么梗

五月一号怎么说早安五月一号早安句子精选

头条怎么才能涨粉

妙奇星球新手初阶怎么玩

水培蔬菜有哪些,适合水培的蔬菜和水果

山楂糕不凝固能回锅重熬吗

会计学专业就业方向与就业前景怎么样

疯人愿原唱是谁疯了疯了伴奏

男子结婚前夕|男子结婚前夕，妻子消失无踪，6年后逛街偶遇，他终于明白了

荔枝放冰箱能保存多久荔枝放冰箱能保存多长时间

秋天来了，女性不想肚子鼓鼓，推荐以下食物，排毒减肥，抗衰老！

家用饭碗可以放烤箱吗

哪种面膜是你的菜

1、两个人在一起|总有一个人会改变自己

因为42岁温峥嵘近照瘦脱相，皮包骨似大头娃娃，面对蛋糕一口不吃

发型不要再披头散发了，脸上有这5个特征的女生，披头发真的很丑