POJ 3613 Cow Relays（floyd+快速幂）

http://poj.org/problem?id=3613

题意：

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

思路：

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

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

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long LL;

 typedef pair<int,int> pll;

 const int inf=0x3f;

 const int maxn=+;

 int n,m,s,t;

 int cnt=;

 map<int,int> ID;

 struct Matrix

 {

     int a[][];

     Matrix operator *(Matrix& t)

     {

         Matrix c;

         memset(c.a,inf,sizeof c.a);

         for(int i=;i<=cnt;i++)

         for(int j=;j<=cnt;j++)

         for(int k=;k<=cnt;k++)

             c.a[i][j]=min(c.a[i][j],a[i][k]+t.a[k][j]);

         return c;

     }

 }base,ans;

 void power()

 {

     ans=base; n--;

     while(n)

     {

         if(n&) ans=ans*base;

         base=base*base;

         n>>=;

     }

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     scanf("%d%d%d%d",&n,&m,&s,&t);

     memset(base.a,inf,sizeof base.a);

     while(m--)

     {

         int u,v,w;

         scanf("%d%d%d",&w,&u,&v);

         if(ID[u])  u=ID[u];  else u=ID[u]=++cnt;

         if(ID[v])  v=ID[v];  else v=ID[v]=++cnt;

         base.a[u][v]=base.a[v][u]=w;

     }

     power();

     printf("%d",ans.a[ID[s]][ID[t]]);

     return ;

 }