poj 3613

题意：

求从一个点s 到一点 e 经过 n 条边的最短路经是多少（可以有重边）

贴一个floyd算法讲解：

http://blog.csdn.net/niushuai666/article/details/6772706

以前一直没仔细想过floyd算法，觉得很简单，今天做这题的时候，看网上的报告都有一句：floyd是每次使用一个中间点k去更新i,j之间的距离，那么更新成功表示i,j之间恰有一个点k时的最短路，如果做N - 1次floyd那么不就是i,j之间借助N - 1 个点时的最短路了。看了很久不明白为什么。也对floyd的最外围的那个k<n产生了疑惑。后来突然想到了，floyd每次更新的都是本身，假如k=3时，dis[1][5]借助dis[1][3]和dis[3][5]成为最短路。不需要去知道1,3之间有多少个点，因为前面已经求出，，（dp?）只知道这一次求出的dis[1][5]多加了一个3这个点。

回到这题，floyd算法是对自身矩阵更新，而这道题却是更新到另一个矩阵上，所以不会出现刚更新过的值又来更新。。例如下面代码的b.mat[1][3] c.mat[3][5]就分别代表上面的dis[1][3],dis[3][5].我们不需要知道tmp.mat[1][5]已经有的点个数。（即已经更新的次数。）只知道，这次更新会加入一个3到他们中间。所以更新k-1次就行。

 1 void floyd(Mat b,Mat c)
 2 {
 3     tmp.init();
 4     for(int k=1;k<=cnt;k++)
 5         for(int i=1;i<=cnt;i++)
 6             for(int j=1;j<=cnt;j++)
 7             {    
 8                 if(b.mat[i][k] <0 || c.mat[k][j] <0)
 9                     continue;
10                 if(tmp.mat[i][j]<0 || tmp.mat[i][j] > b.mat[i][k] + c.mat[k][j]  )
11                      tmp.mat[i][j] = b.mat[i][k] + c.mat[k][j];
12             }
13 }

注意的地方：

1、N次floyd可以用倍增思想加速，就是自底向上的二分。类似求矩阵快速幂（M67大牛）。

2、这里还有一点要注意，T的范围是(2~100),所以最多顶点只有200，而顶点标号的范围却(1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000)。这样我们可以将编号离散化。

3、最后一点这个题的inf要开很大。开始开的是0x5fffffff还是wa了。后来看了某个博客可以把inf定义为-1。就没这个问题了。值得学习。

ps:这道题还是有点似懂非懂.....

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define maxn 205
 9 
10 int n,t,st,en;
11 struct Mat
12 {  
13     int mat[maxn][maxn];  
14     void init()
15     {
16         memset(mat,-1,sizeof(mat));
17     }
18 };  
19 
20 int v[1005];//离散化用
21 Mat ans,tmp,map;
22 int cnt;//顶点个数
23 void init()
24 {
25     int val,s,e;
26     memset(v,0,sizeof(v));
27     cnt=0;
28     ans.init();
29     tmp.init();
30     map.init();
31     for(int i=0;i<maxn;i++)
32         ans.mat[i][i]=0;
33     for(int i=0;i<t;i++)
34     {
35         scanf("%d%d%d",&val,&s,&e);
36         if(v[s]==0)
37         {
38             ++cnt;
39             v[s]=cnt;
40         }
41         if(v[e]==0)
42         {
43             ++cnt;
44             v[e]=cnt;
45         }
46         if(map.mat[v[s]][v[e]]<0 || map.mat[v[s]][v[e]] > val)
47             map.mat[v[s]][v[e]]=map.mat[v[e]][v[s]]=val;
48     }
49 }
50 
51 void floyd(Mat b,Mat c)
52 {
53     tmp.init();
54     for(int k=1;k<=cnt;k++)
55         for(int i=1;i<=cnt;i++)
56             for(int j=1;j<=cnt;j++)
57             {    
58                 if(b.mat[i][k] <0 || c.mat[k][j] <0)//意味着是inf
59                     continue;
60                 if(tmp.mat[i][j]<0 || tmp.mat[i][j] > b.mat[i][k] + c.mat[k][j]  )
61                      tmp.mat[i][j] = b.mat[i][k] + c.mat[k][j];
62             }
63 }
64 
65 Mat copy()
66 {
67     Mat a;
68     for(int i=0;i<=cnt;i++)
69         for(int j=0;j<=cnt;j++)
70             a.mat[i][j]=tmp.mat[i][j];
71     return a;
72 }
73 
74 void solve()
75 {
76     while(n)//虽然这里是n，像是更新了n次。但是下面80行那里第一次调用的时候其实并未更新。只是把map,传递给tmp再转给ans.
77     {
78         if(n&1)
79         {
80             floyd(ans,map);
81             ans=copy();
82         }
83         floyd(map,map);
84         map=copy();
85         n>>=1;
86     }
87 }
88 
89 int main()
90 {
91     while(scanf("%d%d%d%d",&n,&t,&st,&en) != EOF)
92     {
93         init();
94         solve();
95         printf("%d\n",ans.mat[v[st]][v[en]]);
96     }
97     return 0;
98 }