关键词：
题目大意：有n台电脑，m个加速器，每台电脑之间传输文件有一个时间，每个加速器可以使传输时间减半（两台电脑之间可以有多个加速器），求电脑1传输文件到电脑n的最短时间。
解题思路：有些人先求出最短路径，再每次找当前最短路径的最长边用加速器（即贪心），然而这种方法有反例。例如：
3 1
0 3 7
3 0 3
7 3 0
贪心的话求出来的是4.5（1-2-3，在1-2或2-3之间用加速器），然而最优解是3.5（1-3，在1-3之间用加速器）。
正确的解法应该是：最短路径+DP……吧（反正就是有点像最短路径又有点像DP的东西）。
直接上代码，在代码中有注释。
C++ Code：
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const double inf=1e30;//inf表示这两台计算机不能直接传输文件（t）/还没有解（dp）。
int n,m;
double t[51][51][11],dp[51][11];
//t[i][j][k]表示从第i台计算机到第j台用k台加速器的用时，dp[i][j]表示从第1台计算机到第i台用了j台加速器的最短用时。
typedef pair<int,int> pr;//第一个int保存当前的计算机编号，第二个int表示当前用了几台加速器。
queue<pr>q;
void work(){
q.push((pr){1,0});
while(!q.empty()){
int num=q.front().first,jsq=q.front().second;
q.pop();
for(int i=1;i<=n;++i){
if(fabs(t[num][i][0]-inf)>0.000001){
for(int j=jsq;j<=m;++j){//枚举要使用的加速器台数
if(dp[i][j]>dp[num][jsq]+t[num][i][j-jsq]){//DP?SPFA?
dp[i][j]=dp[num][jsq]+t[num][i][j-jsq];
q.push((pr){i,j});
}
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
scanf("%lf",&t[i][j][0]);
if(t[i][j][0]==0)t[i][j][0]=inf;else
for(int k=1;k<=m;++k)t[i][j][k]=t[i][j][k-1]/2;//预处理
}
memset(dp,0,sizeof dp);
for(int i=2;i<=n;++i)
for(int j=0;j<=m;++j)dp[i][j]=inf;
work();
printf("%.2f
",dp[n][m]);//因为用完m个加速器肯定比少用的优，所以答案是dp[n][m]。
return 0;
}
[codevs1243]网络提速
题目大意：有n台电脑，m个加速器，每台电脑之间传输文件有一个时间，每个加速器可以使传输时间减半（两台电脑之间可以有多个加速器），求电脑1传输文件到电脑n的最短时间。解题思路：有些人先求出最短路径，再每次找... 查看详情
网络提速（最短路）
codevs——1243网络提速 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解 题目描述 Description某学校的校园网由n(1<=n<=50)台计算机组成，计算机之间由网线相连，如图5。其中顶点代表计算机，边... 查看详情
codevs1034家园——网络流
由数据范围看是可以用网络流的。。。其实还是接近于很裸的网络流，不过是变成了动态建边，图会很大，不过题目数据范围小啊。。。枚举时间，自己想一个上界，cyc大佬说是100，那就100吧，到达上界前找到就输出当前时间并... 查看详情
codevs1088神经网络
/*这题目简直没谁了我只想说codevs上传题目的专业素养在哪里最起码别有错别字啊0.0咳咳说正事应该是考察拓扑排序的统计出入度然后依次处理每个入度为0的点当然ci为0的可以不必要统计了因为他不传递刺激好好理解一下给出的... 查看详情
codevs1344线型网络
Sol随机化算法+哈密顿路径.好厉害的题...首先都会想到状压DP对吧,复杂度(O(n^22^n)).(n=20) exm??(10^8)有一种算法就是随机化算法再调整.通过随机化算法,再(O(n^2))来调整.调整方式如下:如果有(dis(i-1,i)+dis(j,j+1)>dis(i-1,j)+dis(i,j+1)... 查看详情
洛谷p1038神经网络==codevs1088神经网络
P1038神经网络题目背景人工神经网络（ArtificialNeuralNetwork）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自... 查看详情
codevs1490[ctsc2008]网络管理
...部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部... 查看详情
洛谷p1262间谍网络==codevs4093ez的间谍网络
4093EZ的间谍网络时间限制:10s 空间限制:128000KB 题目等级:黄金Gold题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受... 查看详情
codevs3730无线网络发射选址
题目描述 Description随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平... 查看详情
codevs1922骑士共存问题——网络流
给棋盘黑白染色，源点向不为障碍的奇点连一条权值为1的边，向可以攻击到的偶点连一条边，权值为inf；偶点向汇点（t=n*n+1）连一条权值为1的边。跑最小割，最小割的意义就是看至少要放弃几个点（即这里不放骑士）才能使他... 查看详情
codevs1062路由选择
...目等级:钻石Diamond题目描述 Description 在网络通信中，经常需要求最短路径。但完全用最短路径传输有这样一个问题：如果最终在两个终端节点之间给出的最短路径只有一条。则在该路径中的任一个节点或链路出... 查看详情
codevs1993草地排水
【算法】网络流-最大流(dinic)【题解】网络流：http://m.blog.csdn.net/article/details?id=9401909当前弧优化是因为DFS过程中访问x点时一旦流入量=流出量就退出，所以可以记录下此时正在考虑的弧，下次从此处继续考虑即可。当前弧之前的... 查看详情
51nod1243排船的问题（二分）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1243题意： 思路：二分来做，每次贪心的把船安排到能安排的最左边即可。1#include<iostream>2#include<algorithm>3#include<cstring>4#include<cstdio> 查看详情
2019-07-05·家庭宽带提速换光猫epon改gpon
参考技术A本文关键词:家庭网络接入\\EPON\\GPON\\中国电信天翼智能网关\\烽火HG6201T作为电信浙江地区近十年老用户，免费提速岂不是好事？现有网络是100Mbps电信客服给了我两个升级选项作为上下不对称网络的代表，附上浙江地区... 查看详情
codevs1237&网络流24题餐巾计划（费用流）
题意：一个餐厅在相继的N天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f分；或者送到慢洗部，洗... 查看详情
codevs1269匈牙利游戏(代码片段)
...！布达佩斯（匈牙利首都）的街道形成了一个弯曲的单向网络。Youhavebeenforcedtojoinaraceaspartofa“ 查看详情
51nod1243二分+贪心
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=12431243排船的问题题目来源：Codility基准时间限制：1秒空间限制：131072KB分值:40难度：4级算法题收藏关注一个码头中有N艘船和N个木桩，船的长度为2*X，码头的宽度为M，N个木桩的位... 查看详情
codevs3578无线网络发射器选址==noip2014day2t1
3578无线网络发射器选址时间限制:1s 空间限制:64000KB 题目等级:白银Silver题目描述 Description随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的... 查看详情