网络提速（最短路）
时间限制: 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
数据范围及提示 Data Size & Hint
分类标签 Tags 点此展开
思路：先找出1—n的最短路，再从最短路上，从边的权值的大到小顺序除二知道m==0为止
代码：
#include
using namespace std;
const int maxn=51;
#include
#include
#include
int n,m,p[maxn][maxn],dist[maxn],pre[maxn],visit[maxn]={0},t=0;
double sum=0;
struct Edge{
int from,to;
double weigh;//因为最后结果保存2位小数，所以权值也要是浮点数才行
};
Edge edge[maxn*maxn];//存最短路径的边
void input();
void dijkstra();
int cmp(const Edge &a,const Edge &b)
{
return a.weigh>b.weigh;
}
void stim()
{
while(pre[n]!=0)//把最短路径放到结构体中
{
edge[++t].from=pre[n];
edge[t].to=n;
edge[t].weigh=p[pre[n]][n];
n=pre[n];
}
sort(edge+1,edge+t+1,cmp);//巴结构体的边权有大到小排序
int edgel;
while(m)
{
edgel=1;//比较指针
while(m)
{
while(edge[edgel].weigh>edge[edgel+1].weigh)//把大数一次性除得比第二个数小
{
m--;
edge[edgel].weigh/=2;
if(m==0)return;
}
edgel++;//比较2与3
if(edgel==t) //比到最后一个时，再重新排序，由大到小，分别/2
break;
}
sort(edge+1,edge+t+1,cmp);
}
}
int main()
{
input();
dijkstra();
stim();
for(int i=1;i<=t;++i)
sum+=edge[i].weigh;
printf("%.2lf",sum);
return 0;
}
void dijkstra()
{
visit[1]=1;
pre[1]=0;//把1的前驱设为0
dist[1]=0;//注意
for(int i=2;i<=n;++i)
if(dist[i]<99999)
pre[i]=1; //把前驱是1的先设上，因为下面算法，不会给他设
for(int i=1;i<=n;++i)
{
int min=99999,k=0;
for(int j=1;j<=n;++j)
{
if(dist[j]
{
k=j;
min=dist[j];
}
}
if(k==0) break;
visit[k]=1;
for(int j=1;j<=n;++j)
{
if(dist[j]>dist[k]+p[k][j])
{
dist[j]=dist[k]+p[k][j];
pre[j]=k;//记录前驱
}
}
}
}
void input()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&p[i][j]);
if(p[i][j]==0)
p[i][j]=99999;
if(i==1)
dist[j]=p[i][j];
}
}