floyd算法

六度分离hdu1869ProblemDescription1967年，美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(smallworldphenomenon)”的著名假说，大意是说，任何2个素不相识的人中间最多只隔着6个人，即只用6个人就可以将他们联系在一起，因此他的理论也被称为“六度分离”理论(sixdegreesofseparation)。虽然米尔格兰姆的理论屡屡应验，一直也有很多社会学家对其兴趣浓厚，但是在30多年的时间里，它从来就没有得到过严谨的证明，只是一种带有传奇色彩的假说而已。Lele对这个理论相当有兴趣，于是，他在HDU里对N个人展开了调查。他已经得到了他们之间的相识关系，现在就请你帮他验证一下“六度分离”是否成立吧。Input本题目包含多组测试，请处理到文件结束。对于每组测试，第一行包含两个整数N,M(0N100,0M200),分别代表HDU里的人数（这些人分别编成0~N-1号)，以及他们之间的关系。接下来有M行，每行两个整数A,B(0=A,BN)表示HDU里编号为A和编号B的人互相认识。除了这M组关系，其他任意两人之间均不相识。Output对于每组测试，如果数据符合“六度分离”理论就在一行里输出Yes，否则输出No。SampleInput8701122334455667880112233445566770SampleOutputYesYes每一对顶点间的最短路径Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意两个顶点之间的最短路径？我们可以把Dijkstra算执行n次，每次从不同的顶点开始，则算法时间复杂度为O（n3）。Floyd弗洛伊德给出了另一个算法，时间复杂度也是O（n3），但是形式上简单些。从演示中看算法思想一个简单的图及其邻接矩阵如下：abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)•从上面的D（-1）开始，对于每两个顶点u、v，在D（-1）中存储着一条路径u…v。现在我们考察，试着把a加到u、v的路径上能否，得到一条更短的路径，即如果u…a+a…vu…v的话，能够找到一条更短的路径。abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)c(ca,3)(cc,0)D(0)本来路径上源点或终点就有a的不必考虑。对角线上的也不必考虑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)c(ca,3)(cc,0)D(0)D[b][a]+D[a][c]=6+11D[b][c]=2，所以如果从a绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)D[c][a]+D[a][b]=3+4D[c][b]=∞，所以如果从a绕，更近，那么应该更新。abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)•从上面的D（0）开始，对于每两个顶点u、v，在D（0）中存储着一条路径u…v。现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如果u…b+b…vu…v的话，能够找到一条更短的路径。abc116423abca(aa,0)(ab,4)b(ba,6)(bb,0)(bc,2)c(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)本来路径上源点或终点就有b的不必考虑。对角线上的也不必考虑abc116423abca(aa,0)(ab,4)b(ba,6)(bb,0)(bc,2)c(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)D[a][b]+D[b][c]=6D[a][c]，所以如果从b绕，更近，那么应该更新。abc116423abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)abc116423abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)D[c][b]+D[b][a]=7+6D[c][a]=3，所以如果从b绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)•从上面的D（1）开始，对于每两个顶点u、v，在D（1）中存储着一条路径u…v。现在我们考察，试着把c加到u、v的路径上能否，得到一条更短的路径，即如果u…c+c…vu…v的话，能够找到一条更短的路径。abc116423abca(aa,0)(abc,6)b(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)本来路径上源点或终点就有c的不必考虑。对角线上的也不必考虑abc116423abca(aa,0)(abc,6)b(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)D[a][c]+D[c][b]=6+7D[a][b]=4，所以如果从c绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(abc,6)b(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)abc116423abca(aa,0)(ab,4)(abc,6)b(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)D[b][c]+D[c][a]=2+3D[b][a]=6，所以如果从c绕，更近，那么应该更新。abc116423abca(aa,0)(ab,4)(abc,6)b(bca,5)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)D[b][c]+D[c][a]=2+3D[b][a]=5，所以如果从c绕，更近，那么应该更新。•现在，已经把所有的顶点都试了一遍，算法结束。每两个顶点之间的路径如D(2)所示。abca(aa,0)(ab,4)(abc,6)b(bca,5)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)HDOJ1217汇率税换•SampleInput•3•USDollar•BritishPound•FrenchFranc•3•USDollar0.5BritishPound(0.5倍对换）•BritishPound10.0FrenchFrancFrenchFranc0.21USDollar•3USDollar•BritishPound•FrenchFranc•6•USDollar0.5BritishPound•USDollar4.9FrenchFranc•BritishPound10.0FrenchFranc•BritishPound1.99USDollar•FrenchFranc0.09BritishPound•FrenchFranc0.19USDollar•0•SampleOutput•Case1:Yes（可以不以套汇成功）•Case2:No•for(u=0;un;u++)//中间顶点•for(v=0;vn;v++)//起点•for(w=0;wn;w++)//终点•if(d[v][u]+d[u][w]d[v][w])//新找到一条更短路则更新•{•d[v][w]=d[v][u]+d[u][w];•}00.500010.00.210000.54.91.99010.00.190.0901.050.5255.252.11.0510.500.22050.110251.10250.9950.55.001.990.99510.00.190.0950.95UsbrfrUsBrfrUsBrfrUsbrfrUsbrfrUsbrfrUsBrfrUsBrfr样例1邻接矩阵样例2邻接矩阵样例1最短路径样例2最短路径#includestdio.h#includestring.h#includemath.h#definezero0.000001intmain(){charname[30][300];charfrom[300],to[300];doubleg[30][30];doublerate;intflag;inti,j,k;intn,m;intcases=1;while(scanf(%d,&n)&&n){memset(g,0,sizeof(g));for(i=0;in;i++)g[i][i]=1;for(i=0;in;i++)scanf(%s,name[i]);scanf(%d,&m);for(i=0;im;i++){scanf(%s%lf%s,from,&rate,to);for(j=0;jn;j++)if(strcmp(from,name[j])==0)break;for(k=0;kn;k++)if(strcmp(to,name[k])==0)break;g[j][k]=rate;}for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;j++){rate=g[i][k]*g[k][j];if(g[i][j]rate)g[i][j]=rate;}flag=0;for(i=0;in;i++)if(g[i][i]1){flag=1;br