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

然后我们便得到了从点\(i\)到点\(j\)，经过\(1~k\)条边的最短路。然后我们再用\(ans[i][j]\)处理出这经过\(1~k\)条边的方案中最短的情况。（即最短路中的最短路）
综合以上两种情况，\(ans[i][j]\)就是最终的最短路了。
如果想用以下代码AC，需要做好常数优化，比如\(O2\),\(register\)...
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int inf=1e9;const int N=75;int n,m,a,b,t;int k,q,c,d;int dis[N][N][N];//dis[i][j][k]:经过k条边的前提下，i到j的最短路int ans[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++)for(int k=1;k<=n;k++)dis[i][j][k]=1e9; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=1e9; for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)dis[i][i][k]=0; for(int i=1;i<=n;i++)ans[i][i]=0; for(int i=1;i<=m;i++) {scanf("%d%d%d",&a,&b,&t);dis[a][b][1]=minn(dis[a][b][1],t);ans[a][b]=minn(ans[a][b],t); } scanf("%d%d",&k,&q); if(k>=n) {for(int l=1;l<=n;l++)//l枚举断点{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)//floyed标志性的三层for循环{ans[i][j]=minn(ans[i][j],ans[i][l]+ans[l][j]);//ans[i][j]根据floyed算法的定义，为i到j的最短路}}} } else {k=minn(k,n);for(int l=1;l<=n;l++)//l枚举断点{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)//floyed标志性的三层for循环{for(int p1=1;p1<=k;p1++)//i到l可能的边数{for(int p2=1;p2<=k&&p1+p2<=k;p2++)//l到j可能的边数{dis[i][j][p1+p2]=minn(dis[i][j][p1+p2],dis[i][l][p1]+dis[l][j][p2]);}}}}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=inf;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int l=1;l<=k;l++)ans[i][j]=minn(ans[i][j],dis[i][j][k]); } for(int i=1;i<=q;i++) {scanf("%d%d",&c,&d);if(c==d) puts("0");else if(ans[c][d]==inf) puts("-1");else printf("%d\n",ans[c][d]); } return 0;}继续考虑，若我们能优化掉一层循环，是不是就可以更安稳地A掉这道题了？
依然是以\(k\)作为突破口，有以下策略：“\(k\)越大，答案一定不会更差。”现在我们要利用这种策略，那么上文“令\(dis[i][j][k]\)表示经过\(k\)条边的前提下，\(i\)到\(j\)的最短路”的定义就不合适了。因为我们并不一定要把\(k\)条边走完，\(k\)只是我们做选择时的限制。\(k\)越大，说明限制越宽松。
那么我们的解法便初具雏形了。最外层从\(2\)到\(k\)枚举每一种最大经过的边限制，（为什么不从\(1\)开始枚举？因为最多经过一条边就是相邻两点间的距离了）在循环内跑一个\(floyd\) ，总共四层循环。
剩下的问题就是，转移方程如何设计。首先我们需要明确一点：\(k\)越大，说明选择的面更广，所以每一次的答案，是从上一次的答案加上“新的选择”生成的。
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\).

Autobus 方法记录( 二 )

推荐阅读

带梓的女孩名字及寓意

学生会活动策划方案范文经典学生会活动策划范文

12星座女谁是小野猫谁是小奶猫

月光石手链有什么寓意月光石有什么寓意

粉色的粘土小玫瑰diy

倚的组词倚的组词组

2023武汉中考志愿填报规则详解 2021年武汉中考志愿填报时间

关于深圳市万科教育发展基金会简述深圳市万科教育发展基金会

没有足够的可用内存来运行此程序没有足够的可用内存来运行程序

缓刑是什么意思还要坐牢吗缓刑是什么意思

有一个“撩妹高手”的儿子，是种什么样的体验？

南阳多少人「南阳多少人口2020总人数」

什么是事故车,如何鉴定车子撞到什么程度算事故车

秋季喝什么汤最好秋季喝什么汤最养生

绝地求生刺激战场军团名字怎么改？军团名字修改攻略[多图]

梦见大鱼吃小鱼

文房四宝指什么文房四宝指什么数字

OPPO Reno6简单评测 oppo reno6有nfc吗

怎么判断二手车的真实行驶里程? 要看哪些细节

双子座成功人士知多少？