hdu3665Floyd解法

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/3665/

Floyd是经典的dp算法，将迭代过程分成n个阶段，经过n个阶段的迭代所有点对之间的最短路径都可以求出，时间复杂度是O(n^3)。

代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned int ui;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 #define pf printf
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 #define prime1 1e9+7
 9 #define prime2 1e9+9
10 #define lson l,mid,rt<<1
11 #define rson mid+1,r,rt<<1|1
12 #define scand(x) scanf("%llf",&x) 
13 #define f(i,a,b) for(int i=a;i<=b;i++)
14 #define scan(a) scanf("%d",&a)
15 #define mp(a,b) make_pair((a),(b))
16 #define P pair<int,int>
17 #define dbg(args) cout<<#args<<":"<<args<<endl;
18 #define inf 0x3f3f3f3f
19 const int maxn=1e3+5;
20 int n,m,t;
21 int edge[maxn][maxn],d[maxn][maxn];
22 int ans=inf;
23 void init()
24 {
25     f(i,0,n)
26         f(j,0,n)
27         {
28             if(i==j)d[i][j]=0;
29             else d[i][j]=inf;
30         }
31 }
32 void floyd()
33 {
34     f(k,0,n)
35         f(i,0,n)
36             f(j,0,n)
37             {
38                 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
39             }
40 }
41 int main()
42 {
43     //freopen("input.txt","r",stdin);
44     //freopen("output.txt","w",stdout);
45     std::ios::sync_with_stdio(false);
46     while(scan(n)!=EOF)
47     {
48         init();
49         int mi,pi;
50         f(i,0,n-1)
51         {
52             scan(mi);
53             scan(pi);
54             if(pi)d[i][n]=0;
55             int u,v;
56             while(mi--)
57             {
58                 scan(u);
59                 scan(v);
60                 d[i][u]=v;
61             }
62         }
63         floyd();
64         pf("%d
",d[0][n]);
65      } 
66  }