最短路径问题Floyed-Warshall算法time limit :10000 msmemorylimit 336065536 k
总提交：559加速：309
Case Time Limit:1000MS
Description
平面上有n个点(N=100 )，每个点的坐标都在- 10000到10000之间。 在几个点之间有连接。 如果有连接，表示可以从一点到达另一点。 也就是说，两点之间有通路，通路的距离是两点直线的距离。 现在的任务是找到从一点到另一点的最短路径。
Input
输入short.in文件。 一共是n m 3行。 现在，我们看到：
第一行是整数n。
从第2行到第n 1行，共计n行，每行的两个整数x和y用一个空格分隔一个点的坐标。
第n 2行是整数m，表示图中的连接数。
接下来的m行每行编写一个连接，由两个整数I、j组成，表示第I点和第j点之间存在连接。
最后一行：表示源点和目标点的两个整数s和t。
Output
输出文件short.out只包含一行实数，表示从s到t的最短路径长度。
Sample Input
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
样品输出
3.41
问题解决思路浮动封装算法：
简称Floyed (弗洛伊德)算法是最简单的最短路径算法，可以计算图中任意两点之间的最短路径。 Floyed的时间复杂度为o(n3 )，适用于产生负边缘的情况。
思想说明：
三层环、第一层环的中间点k、第二层环的起点终点I、j，在从点I到点k的距离和从点k到点j的距离小于从原来的点I到点j的距离的情况下，用该短路径长度更新从原来的点I到点j的距离的算法思路很容易理解
(用这个方法也可以判断一张图中的两点是否相连。 ）
代码# include iostream # include cstdio # include cmath # includeiomanipusingnamespacestd； int n，n1，s，t，x，y； double f[200][200]，a[200][3]； //dis[i][j]是从I到j的最短路径。 int main () memset(f ) f、0X7f、sizeof(f ) )； scanf('%d '，n )； for(intI=1； i=n； I ) cina[i][1]a[i][2]； scanf('%d '，n1 )； for(intI=1； i=n1； I ) { cinxy； f [ y ] [ x ]=f [ x ] [ y ]=sqrt (double (a [ x ] [1]-a [ y ] [1]，2 ) pow ) double ) a [ x ]-a [2] () cinst for(intk=1； k=n； k ) for(intI=1； i=n； I ) for(intj=1； j=n； j () if ) ) (I！=j () ) I！=k () k！=j ) ) f[I][j]f[I][k]f[k] () ) f ) I )=f[I][k]f[k][j]； }coutfixedsetprecision(2) f[s][t]； }