【Warshall_Floyd】

模板：
 1 /*
 2  Problem: 任意两点间的最短路
 3  Tips   : 可以处理边时负数的情况。
 4           判断图中是否有负圈，只需检查d[i][j]是负数的顶点i就可以。
 5  复杂度 : O(n^3)
 6 */
 7 
 8 #include <iostream>
 9 #include <cstring>
10 #include <cstdlib>
11 #include <cstdio>
12 #include <queue>
13 #include <vector>
14 #include <algorithm>
15 using namespace std;
16 const int MAX_V = 505；
17 int d[MAX_V][MAX_V]; //d[i][j]表示边e(i,j)的权值，不存在时为inf，d[i][i]=0;
18 int V, E;
19 
20 void Warshall_Floyd()
21 {
22     for(int k = 0; k < V; k++)
23         for(int i = 0; i < V; i++)
24             for(int j = 0; j < V; j++)
25                 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
26 
27 }
28 
29 int main()
30 {
31 
32     return 0;
33 }
Warshall_Floyd