Nostop

Description

M国有N个城市，H条单向的道路，AekdyCoin从编号为1的城市出发，每经过一条道路要花一个单位的时间。假设他出发的时刻为0，他需要在K时刻到达编号为N的城市。并且，AekdyCoin不会在一个城市停留，每到一个城市他要立刻往下一个城市出发，最后在K时刻时他必须在城市N。虽然AekdyCoin经过任意一条道路的花费的时间都是1，但是每条道路的过路费不一定相同。现给出每条道路的过路费，问AekdyCoin从编号为1的城市出发，在K时刻到达编号为N的城市最小需要花费多少钱？注意AekdyCoin可以经过同一个城市任意多次，包括城市N。

Input

第一行输入一个整数T表示数据组数，接下来输入T组数据。对于每组数据，第一行输入三个整数N，H,K(1<=N<=50,1<=H<=3000,1<=K<=1000000000)，接下来输入H行，每行三个整数u、v、cost（1<=u,v<=n,1<=cost<=1000000），表示从u到v过路费为cost的一条单行道。

Output

对于每组数据输出一行一个整数表示最小花费，若无法在K时刻到达城市N，则输出-1。

Sample Input

15 5 31 2 12 5 11 3 103 4 104 5 10

Sample Output

30

还记得当年oi的时候在矩阵乘法的论文看到过和这个一样的题，但是……当年自己too young too simple，就没认真看那篇论文……

要想把这个题转化成矩阵乘法，还略有一点难度

首先我们知道若。f [i] [j]表示通过i条边的路径到达某个点j，最短距离是多少，则：f [i] [j] =min(f [i-1] [k] +G[k， j])

乍一看跟矩阵乘法一点关系都扯不上

但是

由于矩阵乘法的递推式是

阵乘法是基于以下递推式：f（i，j）  = sum(f(i, k) * f(k, j))

看一下觉得这两者之间还是有相似性的——只是把乘法变成了加法，把求和变成了求最小值……

然后那篇国家集训队论文上是证明了这样变化以后还是满足结合律……orz

感觉这个挺好理解的（（AB）C = A（BC））

然后就真的神奇的转换成矩阵乘法了…………吓哭


如果还不理解，请去搜索矩阵乘法国家集训队论文（貌似是2008年的?）

送一道题——bzoj1297（scoi2009迷路）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF -1
const int  N = 55;
int n, h, k;
struct matrix
{
  long long p[N][N];
  int n;
  //matrix(){
  //    for (int i = 1; i <= N; i++)
  //    for (int j = 1; j <= N; j++)
  //      p[i][j] = INF;
  //}
}ans, a;
matrix operator * (matrix a, matrix b)
{
    matrix c;
    c.n = a.n;
    for (int i = 1; i <= c.n; i++)
        for (int j = 1; j <= c.n; j++)
            c.p[i][j] = INF;
    for (int i = 1; i <= a.n; i++)
      for (int j = 1; j <= b.n; j++)
        for (int k = 1; k <= a.n; k++)
        {
            if(a.p[i][k]==INF||b.p[k][j]==INF) continue;
            if(c.p[i][j]==INF||c.p[i][j]>a.p[i][k]+a.p[k][j])
            c.p[i][j] = a.p[i][k] + b.p[k][j];
        }
    return c;
  }

matrix quick(matrix m, int n)
{
    matrix ans = a;
    n--;
    while(n)
    {
        if(n & 1) ans = m * ans;
        m = m * m;
        n >>= 1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &h, &k);
        a.n = n;
        for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a.p[i][j] = INF;

        for (int i = 1; i <= h; i++)
        {
            int x, y;
            long long z;
            scanf("%d%d", &x, &y);
            cin >> z;
            if(a.p[x][y]==INF||z<a.p[x][y])
                a.p[x][y] = z;
        }
        ans = quick(a, k);

        cout << ans.p[1][n]<< endl;;

    }
    return 0;
}