题目描述 Description
某学校的校园网由n(1<=n<=50)台计算机组成，计算机之间由网线相连，如图5。其中顶点代表计算机，边代表网线。正如你所见，不同网线的传输能力不尽相同，例如计算机1与计算机2之间传输信息需要34秒，而计算机2与计算机3之间的传输信息只要10秒。计算机1与计算机5之间传输信息需要44秒，途径为机1到机3到机5。
现学校购买了m(1<=m<=10)台加速设备，每台设备可作用于一条网线，使网线上传输信息用时减半。多台设备可用于同一条网线，其效果叠加，即用两台设备，用时为原来的1/4，用三台设备，用时为原来的1/8。如何合理使用这些设备，使计算机1到计算机n传输用时最少，这个问题急需解决。校方请你编程解决这个问题。例如图5，若m=2，则将两台设备分别用于1-3，3-5的线路，传输用时可减少为22秒，这是最佳解。
输入描述 Input Description
第一行先输入n,m。以下n行，每行有n个实数。第i行第j列的数为计算机i与计算机j之间网线的传输用时，0表示它们之间没有网线连接。注意输入数据中，从计算机1到计算机n至少有一条网路。
输出描述 Output Description
输出计算机1与计算机n之间传输信息的最短时间。(保留两位小数)
样例输入 Sample Input
5 2
0 34 24 0 0
34 0 10 12 0
24 10 0 16 20
0 12 16 0 30
0 0 20 30 0
样例输出 Sample Output
22.00
题解：a[i][j][k]表示从i到j使用k个加速器所需的时间。用spfa找最短路即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 60
#define M 15
const double Max=1.0e+10;
using namespace std;
int n,m;
double a[N][N][M],f[N][M];
bool ff[N]={};
int w[N*N];
void spfa()
{
int head(),tail(),u;
w[]=;
ff[]=;
do
{
head++;
u=w[head];
ff[u]=;
for (int i=;i<=n;i++)
if (i!=u)
for (int j=;j<=m;j++)//从1到u使用j个加速器
for (int k=;k<=m-j;k++)//从u到i使用k个加速器，同时要保证j+k<=m
if (f[u][j]+a[u][i][k]<f[i][j+k])
{
f[i][j+k]=f[u][j]+a[u][i][k];
if (!ff[i]) w[++tail]=i,ff[i]=;
}
}while (head<tail);
}
int main()
{
scanf("%d%d",&n,&m); for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
scanf("%lf",&a[i][j][]);
if (!a[i][j][])
for (int k=;k<=m;k++)
a[i][j][k]=Max;
else
for (int k=;k<=m;k++)
a[i][j][k]=a[i][j][k-]/;
} for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
f[i][j]=Max; spfa(); printf("%.2lf",f[n][m]); return ;
}
spfa