首页 > 代码库 > codevs 1243 网络提速
codevs 1243 网络提速
题目描述 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
数据范围及提示 Data Size & Hint
题解:好久没做关于最短路的题目了。感觉自己都不会打了。先做点稍微简单一点的。spfa。f[i][j]表示从1到i用j个加速最短时间。
#include <cstdio>#define N 55const double M=100000000009.0;int n,m,a[N*N],b[N];double t[N][N][N],f[N][N];int main(){ scanf("%d%d",&n,&m); int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%lf",&t[i][j][0]); if(i==j) continue; if(!t[i][j][0]) for(k=0;k<=m;k++) t[i][j][k]=M; else for(k=1;k<=m;k++) t[i][j][k]=t[i][j][k-1]/2; } for(i=2;i<=n;i++) for(j=0;j<=m;j++) f[i][j]=M; a[1]=b[1]=1; for(int h=1,t1=1,now;h<=t1;h++) { now=a[h]; for(i=1;i<=n;i++) if(i!=now) for(j=0;j<=m;j++) for(k=0;k<=m-j;k++) if(f[now][k]+t[now][i][j]<f[i][j+k]) { f[i][j+k]=f[now][k]+t[now][i][j]; if(!b[i]) b[i]=1,a[++t1]=i; } b[now]=0; } printf("%.2lf",f[n][m]);}
codevs 1243 网络提速
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。