题解 CF187B 【AlgoRace】
frankchenfu
2018-04-06 15:37:22
我们考虑动态规划。
------------
假设我们已经知道了
* $i\to j$只用第$k$部车的最短时间为$g_{i,j,k}$；
* 并且设$f_{i,j,p}$表示$(i,j)$**换$p$次车**的最短时间。
于是我们考虑使用`Floyd`算法，可以得到转移方程：
### $$f_{i,j,p}=\displaystyle\min_{k}^{k\in V}\{f_{i,k,p-1}+f_{k,j,0}\}$$
这是什么意思呢？一般的`Floyd`在进行松弛操作的时候，并不需要考虑这里的$p$，而在这里，我们发现每次松弛操作的时候，都需要“换一次车”。这也就意味着，如果我们要求换$p$次车的最小值，一定是换$p-1$次车之后，再换一次车。而前$p-1$次换车对应的就是$i\to k$，而最后再换一次车$k\to j$。
这样，我们通过$1000$次（询问中$k$的最大值）`Floyd`就可以求出答案了。那么$g_{i,j,k}$怎么求呢？很简单，读入之后做$m$次`Floyd`即可。这样这个算法就结束了，时间复杂度为$O(k_{\max}\cdot n^3)=2.16\times 10^8$，看起来勉强可以通过2000ms的实现，然后最后我`TLE 36`了（加上优化之后仍然`TLE 53`）.所以我们有没有什么好的办法进一步优化呢？
------------
其实算法上并不需要优化！
我们注意到因为只有$60$个城市，所以换车次数不会超过$60$，那么我们把$k_{\max}$就可以可看做是$60$，于是$O(k_{\max}\cdot n^3)=60^4=1.296\times 10^7$.于是就很愉快地通过了。
------------
```cpp
#include<cstdio>
#include<cstring>
#include<assert.h>
#define NDEBUG
const int MAXN=65,MAXK=1010;
const int MAXQ=100010;
int n,m,r,max_k=1<<31;
int f[MAXN][MAXN][MAXK],g[MAXN][MAXN][MAXN];
int q[MAXQ][3];
//f_{i,j,k}=(i,j)换k次车. g_{k,i,j}=(i,j)用第k种车直接跑.
inline int max(int x,int y){
return x>y?x:y;
}
inline int min(int x,int y){
return x<y?x:y;
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d%d%d",&n,&m,&r);
for(int k=1;k<=m;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&g[k][i][j]);
for(int i=1;i<=r;i++){
scanf("%d%d%d",&q[i][0],&q[i][1],&q[i][2]);
max_k=max(max_k,q[i][2]);
}
max_k=min(max_k,n);
//floyd O(m* n^3)=O(n^4)=1.296e+7;
for(int p=1;p<=m;p++)
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[p][i][j]=min(g[p][i][j],g[p][i][k]+g[p][k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j][0]=~(1<<31);
for(int k=1;k<=m;k++)//初值：不换车，从头跑到尾.
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j][0]=min(f[i][j][0],g[k][i][j]);
for(int p=1;p<=max_k+1;p++){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j][p]=f[i][j][p-1];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j][p]=min(f[i][j][p],f[i][k][p-1]+f[k][j][0]);
}
for(int i=1;i<=r;i++){
q[i][2]=min(q[i][2],max_k);
printf("%d\n",f[q[i][0]][q[i][1]][q[i][2]]);
}
return 0;
}
```