POJ 3613 Cow Relays（floyd+快速幂）

题意：

求经过k条路径的最短路径。

思路：

如果看过《矩阵乘法在信息学的应用》这篇论文就会知道

现在我们在邻接矩阵中保存距离，那么按照上面计算，不就是k路径的最短路径了吗？

每次用folyd去最小值，至于k次就是相乘，用快速幂。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 using namespace std;
11 typedef long long LL;
12 typedef pair<int,int> pll;
13 const int inf=0x3f;
14 const int maxn=120+5;
15 
16 int n,m,s,t;
17 int cnt=0;
18 map<int,int> ID;
19 
20 struct Matrix
21 {
22     int a[205][205];
23     Matrix operator *(Matrix& t)
24     {
25         Matrix c;
26         memset(c.a,inf,sizeof c.a);
27         for(int i=1;i<=cnt;i++)
28         for(int j=1;j<=cnt;j++)
29         for(int k=1;k<=cnt;k++)
30             c.a[i][j]=min(c.a[i][j],a[i][k]+t.a[k][j]);
31         return c;
32     }
33 }base,ans;
34 
35 void power()
36 {
37     ans=base; n--;
38     while(n)
39     {
40         if(n&1) ans=ans*base;
41         base=base*base;
42         n>>=1;
43     }
44 }
45 
46 int main()
47 {
48     //freopen("D:\input.txt","r",stdin);
49     scanf("%d%d%d%d",&n,&m,&s,&t);
50     memset(base.a,inf,sizeof base.a);
51     while(m--)
52     {
53         int u,v,w;
54         scanf("%d%d%d",&w,&u,&v);
55         if(ID[u])  u=ID[u];  else u=ID[u]=++cnt;
56         if(ID[v])  v=ID[v];  else v=ID[v]=++cnt;
57         base.a[u][v]=base.a[v][u]=w;
58     }
59     power();
60     printf("%d",ans.a[ID[s]][ID[t]]);
61     return 0;
62 }