乐陵seo网站,多屏合一网站建设,深圳定制巴士怎么买票,广告片题目链接#xff1a;http://hihocoder.com/problemset/problem/1089 算法描述#xff1a; floyd算法是求解图中任意两点最短路的经典算法#xff0c;复杂度为O(n^3)。虽然我们完全可以用n次dijkstra算法来求任意两点的最短路#xff0c;复杂度也是O(N^3)#xff0c;但如果… 题目链接http://hihocoder.com/problemset/problem/1089 算法描述 floyd算法是求解图中任意两点最短路的经典算法复杂度为O(n^3)。虽然我们完全可以用n次dijkstra算法来求任意两点的最短路复杂度也是O(N^3)但如果有一个算法只需要5行代码就可以完成我们想做的事情我们有什么理由不用它 floyd算法主要用了动态规划的思想 设d[i][j]表示i到j的最短路径的长度, 那么我们可以这样来求解d[i][j]: 1首先i到j的路径只允许经过节点1那么d[i][j] min(d[i][j], d[i][1]d[1][j]); 2然后我们逐步放开限制i到j的路径只允许经过点1,2, 那么在1的基础上继续更新d[i][j]的值有d[i][j] min(d[i][j], d[i][2]d[2][j]); ....... 注意逐步放开限制的过程 写成代码就5行 1 for(int k1; kn; k)
2 for(int i1; in; i)
3 for(int j1; jn; j)
4 if(i!jj!kd[i][k]!INFd[k][j]!INF)
5 d[i][j] min(d[i][j], d[i][k]d[k][j]); 我的完整代码 1 #include iostream2 3 using namespace std;4 5 #define MAXN 1056 #define INF 0x7fffffff7 8 int d[MAXN][MAXN], n, m;9
10 void init()
11 {
12 for(int i1; in; i) d[i][i] 0;
13 for(int i1; in; i) for(int j1; jn; j) if(i!j) d[i][j] INF;
14 }
15
16 void floyd()
17 {
18 for(int k1; kn; k)
19 for(int i1; in; i)
20 for(int j1; jn; j)
21 if(i!jj!kd[i][k]!INFd[k][j]!INF)
22 d[i][j] min(d[i][j], d[i][k]d[k][j]);
23 }
24
25 int main()
26 {
27 while(cinnm)
28 {
29 init();
30 while(m--)
31 {
32 int u, v, w;
33 cinuvw;
34 d[u][v] d[v][u] min(w, d[u][v]);
35 }
36 floyd();
37 for(int i1; in; i)
38 {
39 for(int j1; jn; j) coutd[i][j] ;
40 coutd[i][n]endl;
41 }
42 }
43 return 0;
44 } 转载于:https://www.cnblogs.com/pczhou/p/4297629.html
