FOJ 2173 Nostop 從1點到n點恰好走了k次的最短路

思路：

類似於傳遞閉包的性質

用矩陣mp[i][j] 表示i點到j點 走1次的最短路

--------------

若我們用 mp[i][j] 表示從i點到j點 走了k次的最短路距離

那麼我們要通過 矩陣mp 得到 矩陣 ret[u][v] 表示 u->v 走了2*k次的最短路

就是：

mp[u][i] + mp[i][v]; i為任意點（即1-n）

顯然我們轉換一下上式就是：

ret[u][v] = inf;
for(int i = 1; i <= n; i++)
ret[u][v] = min(ret[u][v], mp[u][i]+mp[i][v]);

然後求出整個的ret矩陣就是：

for(int u = 1; u<=n; u++)
	for(int v = 1; v<=n; v++){
		ret[u][v] = inf;
		for(int i = 1; i <= n; i++)
			ret[u][v] = min(ret[u][v], mp[u][i]+mp[i][v]);
}

#include
#include
#include
#include
#include
using namespace std;
#define Matr 55 //矩陣大小,注意能小就小
#define ll long long

#define N 52
#define inf 100000000000000000
struct mat{//矩陣結構體，a表示內容，size大小 矩陣從1開始
	ll a[Matr][Matr];
	int size;
};
mat multi(mat m1,mat m2)//兩個相等矩陣的乘法，對於稀疏矩陣，有0處不用運算的優化 
{
	mat ans;ans.size=m1.size;
	for(int i=1;i<=m1.size;i++)
		for(int j=1;j<=m2.size;j++)
		{
			ll tmp = inf;
			for(int k = 1; k <= m1.size; k++)
				tmp = min(tmp, m1.a[i][k] + m2.a[k][j]);
			ans.a[i][j]=tmp;
		}
	return ans;
}
mat quickmulti(mat m,int n){
	mat ans=m;
	n--;
	while(n){
		if(n&1)ans=multi(m,ans);
		m=multi(m,m);
		n>>=1;
	}
	return ans;
}
mat mp;
int n, m, k;

int main(){
	int u, v, i, j, T; scanf(%d,&T);
	ll d;
	while(T--){
		scanf(%d %d %d,&n,&m,&k);
		for(i=1;i<=n;i++)for(j=1;j<=n;j++)mp.a[i][j] = inf;
		mp.size = n;
		while(m--){
			scanf(%d %d,&u,&v); cin>>d;
			mp.a[u][v] = min(mp.a[u][v], d);
		}
		mat ans = quickmulti(mp,k);
		if(ans.a[1][n]==inf)puts(-1);
		else cout<