题意：
求无向图s,t点间经过L条边的最短路。
思路：
矩阵连乘求图中任意两点间的最短路不经常用，因为复杂度是N^3logN的，但这种算法对最短路径经过的路径数的描述却非常清晰，尤其当需经过路径L比较大而顶点数N比较小的时候，N^3logL就比较可观了,求最短路径的特殊矩阵乘法满足结合律，可以幂乘加速。很有意思的是：把两个mul函数中的k循环放到i,j之外后整个算法就变成了倍增floyd算法（倍增floyd每次不用min(g[i][j],g[i][k]+G[k][j])更新g[i][j]有别于floyd算法），结果复杂度都一样。理解倍增floyd有助于理解floyd中动态规划的特点。
代码：
//poj 3613
//sepNINE
#include <iostream>
#include <map>
using namespace std;
const int maxN=512;
int g[maxN][maxN];
int ans[maxN][maxN];
int tmp[maxN][maxN];
map<int,int> mymap;
int n;
void mul1()
{int i,j,k;for(i=1;i<=n;++i)for(j=1;j<=n;++j){tmp[i][j]=INT_MAX;for(k=1;k<=n;++k)if(ans[i][k]!=-1&&g[k][j]!=-1)tmp[i][j]=min(tmp[i][j],ans[i][k]+g[k][j]);}for(i=1;i<=n;++i)for(j=1;j<=n;++j)ans[i][j]=tmp[i][j]==INT_MAX?-1:tmp[i][j];return ;
}
void mul2()
{int i,j,k;for(i=1;i<=n;++i)for(j=1;j<=n;++j){tmp[i][j]=INT_MAX;for(k=1;k<=n;++k)if(g[i][k]!=-1&&g[k][j]!=-1)tmp[i][j]=min(tmp[i][j],g[i][k]+g[k][j]);}for(i=1;i<=n;++i)for(j=1;j<=n;++j)g[i][j]=tmp[i][j]==INT_MAX?-1:tmp[i][j]; return ;
} int main()
{int i,L,m,s,e;memset(g,-1,sizeof(g));scanf("%d%d%d%d",&L,&m,&s,&e);n=0;while(m--){int w,a,b;scanf("%d%d%d",&w,&a,&b); if(mymap[a]==0) mymap[a]=++n;if(mymap[b]==0) mymap[b]=++n;g[mymap[a]][mymap[b]]=g[mymap[b]][mymap[a]]=w;}memset(ans,-1,sizeof(ans));for(i=1;i<=n;++i)ans[i][i]=0;while(L){if(L%2==1)mul1();//ans=ans*g;mul2();//g=g*g; L=L/2;}printf("%d",ans[mymap[s]][mymap[e]]);
}