时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold
题目描述 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
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 #define MAX 1000120 7 int n,m,dis[55]; 8 queue<int> q; 9 double map[55][55][10],f[60][15]; 10 bool exist[55]; 11 void SPFA() 12 { 13 memset(dis,0,sizeof(dis));memset(exist,false,sizeof(exist)); 14 q.push(1);exist[1]=true;dis[1]=1; 15 while(!q.empty()) 16 { 17 int u=q.front();q.pop();exist[u]=false; 18 for(int i=1;i<=n;i++){ 19 if(i!=u){ 20 for (int j=0;j<=m;j++)//从1到u使用j个加速器 21 for (int k=0;k<=m-j;k++)//从u到i使用k个加速器，同时要保证j+k<=m 22 if (f[u][j]+map[u][i][k]<f[i][j+k]){ 23 f[i][j+k]=f[u][j]+map[u][i][k]; 24 if(!exist[i]){ 25 q.push(i);exist[i]=true; 26 } 27 } 28 } 29 } 30 } 31 } 32 int main() 33 { 34 scanf("%d%d",&n,&m); 35 for(int i=1;i<=n;i++){ 36 for(int j=1;j<=n;j++){ 37 scanf("%lf",&map[i][j][0]); 38 if(!map[i][j][0]){ 39 for(int k=0;k<=m;k++) 40 map[i][j][k]=MAX; 41 } 42 else{ 43 for(int k=1;k<=m;k++) 44 map[i][j][k]=map[i][j][k-1]/2.0; 45 } 46 } 47 } 48 for(int i=2;i<=n;i++) 49 for(int j=0;j<=m;j++) 50 f[i][j]=MAX; 51 SPFA(); 52 printf("%.2lf",f[n][m]); 53 return 0; 54 }