原题： FZU 2173 http://acm.fzu.edu.cn/problem.php?pid=2173
一开始看到这个题毫无头绪，根本没想到是矩阵快速幂，其实看见k那么大，就应该想到用快速幂什么的，况且n<=50，可以用矩阵来表示图。
1.为什么能用矩阵快速幂呢？
原理：
原始矩阵m[][]中，m[u][v]代表u到v的花费，求矩阵的k次幂后，此时m[u][v]代表，从u走向b经过v步的最少花费
注意此时矩阵的相乘应该写成：
m[a][b]=min(m[a][1]+m[1][b],...m[a][n]+m[n][b]) ，即取最小值而非相加。
2.为什么呢？
m的1次方，无疑是正确的。
m的2次方
此时(m[a][b])^2=min(m[a][1]+m[1][b],..m[a][n]+m[n][b])，就是枚举a经过1到n点再到b的最少花费，就是a经过两步到达b的最少花费
归纳法：
如果(m[a][b])^i代表了a走i步到达b的最少花费，则m^(i+1)=min((m[a][1])^i+m[1][b],...(m[a][n])^i+m[n][b])
所以可以这样做。
（借鉴nothing的博客）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define Mod 1000000007
#define lll __int64
using namespace std;
#define N 6007 struct Matrix
{
lll m[][];
};
int n,h,k; Matrix Mul(Matrix a,Matrix b)
{
Matrix c;
memset(c.m,-,sizeof(c.m));
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
for(int k=;k<n;k++)
{
if(a.m[i][k]!=-&&b.m[k][j]!=-)
{
if(c.m[i][j] == -)
c.m[i][j] = a.m[i][k]+b.m[k][j];
else
c.m[i][j] = min(c.m[i][j],a.m[i][k]+b.m[k][j]);
}
}
}
return c;
} Matrix fastm(Matrix a,int n)
{
if(n == )
return a;
Matrix res = fastm(a,n/);
res = Mul(res,res);
if(n&)
res = Mul(res,a);
return res;
} Matrix MPow(Matrix a,int n) //第二种写法
{
Matrix res = a;
n--;
while(n)
{
if(n&)
res = Mul(res,a);
n>>=;
a = Mul(a,a);
}
return res;
} int main()
{
int t,i,j,k;
int u,v;
lll w;
Matrix A,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&h,&k);
memset(A.m,-,sizeof(A.m));
for(i=;i<h;i++)
{
scanf("%d%d%I64d",&u,&v,&w);
u--,v--;
if(A.m[u][v] == -)
A.m[u][v] = w;
else
A.m[u][v] = min(A.m[u][v],w);
}
ans = MPow(A,k);
printf("%I64d\n",ans.m[][n-]);
}
return ;
}