目录

Description

        原题面

        更简洁的题面

Format

Input

Output

Samples

输入数据

输出数据

分析

代码

原题面

塞内加尔是非洲的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它--它实在是个太小、太贫穷的国家了。可是，就是这个人口不足900万、全国仅有2个标准足球场地的小国，在2002韩日世界杯的非洲区预选赛中脱颖而出，取得了世界杯决赛圈的入场券（幸好，去年中国队也进入了世界杯决赛圈，不然可就丢脸了）。 在塞内加尔全国球迷欣喜若狂，世界足球行家大跌眼镜的同时，塞内加尔足协却发现自己面临着一个颇为尴尬的问题--说起来令人不可思议，由于打非洲区预选赛时四处征战，加上足协经营不力，现在足协的预算以几近赤字--也就是说，塞内加尔足协支付不起从本国乘飞机到达韩国参加世界杯的费用！经过三思，塞内加尔足协向非洲足联递交了一份《关于减免球队旅行费用》的申请；可是--众所周知的，非洲足联也是惨淡经营，幸好非洲足联秘书长神通广大，弄来了M张优惠乘机券：每张优惠券可以作用于一条航线，使全队通过此航线的费用减半；多张优惠券用于同一条线路，其效果叠加--即在一条航线上用两张优惠券，其费用降为原费用的1/4，依此类推。

塞内加尔足球队要从塞内加尔国家机场出发，途经一些中转机场，最后要到达韩国釜山机场。为了合理地分配各张优惠券，使得所需费用最少，塞内加尔足协找到了你，请你编程解决这个问题。

更简洁的题面

有一堆点和一堆单向边，你可以通过m次某种操作，每次可以使一条单向边的边权变为原来的一半，求1号点到n号点的最短距离。

Format

Input

第1行有两个数N、M（0 < N < = 70，0 < = M < = 20）并用空格隔开

分别表示包括起点（塞内加尔国家机场）（1）、终点（韩国釜山机场）（n）的机场数，以及塞内加尔足协现有的优惠券数量。

从第2行到第N+1行起，每行有N个数，其中第I行的第J个数代表从机场I到机场J所需费用；为零的数代表两机场无航线。

假设起点标号为1，终点标号为N。

Output

第1行仅有一个数（输出整数部分），代表所求得的从机场1到机场N的最小费用；

Samples

输入数据

5 2
0 0 80 96 0
70 0 72 54 0
18 0 0 99 82
72 18 71 0 0
69 0 0 70 0

输出数据

81

分析

这道题可挺啰嗦的。

首先，我们一定要进行m次操作，才能取得最优解

然后，你不由自主地想起了mst的prim做法。

在prim中，我们有一个数组f[i]，记录i到mst的距离。

那么，我们可以想到，假如f[i]表示i到1的距离，又假如点i通过j与mst相连，那么i到1的距离就是i、j之间的距离加上f[j]的和及f[i]的较小值。

我们可以用prim来进行类比。

每次选取一个最小的f[i]，记录i和f[i]，同时更新与i相连的所有点的f。

等等，是不是少了些什么？m次操作呢？

因为多出了这m次操作，我们的一维数组f不够用了。

一维数组不够用就用二维数组呗！

那么，它应该成为一个二维数组——f[i][j]，表示当执行j次操作时，i到1的最短距离。

那么，具体思路就成了——每次选取一个最小的f[i][j]，记录i、j和f[i]，同时通过从j枚举到m，更新与i相连的所有点的f[i][...]。

另外，题目中似乎并没有说从a到b的距离等于从b到a的距离…………

好一个动态规划…………

代码

#include
using namespace std;
const int N=200;
int n,m,way[N][N];
double f[N][N];
bool ch[N][N]; 
int g,pri,lon;
double ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>way[i][j];
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			f[i][j]=1e9;
	f[1][0]=0;
	for(;;)
	{
		ans=1e9;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=m;j++)
				if(ans>f[i][j]&&!ch[i][j])
					g=i,pri=j,ans=f[i][j];
		if(ans==1e9)
			break;
		ch[g][pri]=true;
		for(int i=1;i<=n;i++)
			for(int j=pri;j<=m;j++)
				if(way[g][i]&&!ch[i][j])
					f[i][j]=min(f[i][j],ans+way[g][i]*1.0/(1<