牛站（矩阵乘法，类floyd：边数限制的最短路问题）

牛站（矩阵乘法，类floyd：边数限制的最短路问题）

给定一张由T条边构成的无向图，点的编号为1~1000之间的整数。

求从起点S到终点E恰好经过N条边（可以重复经过）的最短路。

注意: 数据保证一定有解。

输入格式

第1行：包含四个整数N，T，S，E。

第2..T+1行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

输出格式

输出一个整数，表示最短路的长度。

数据范围

2≤T≤100,
2≤N≤10^6

输入样例：

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例：

10

思路：这道题在最短路的基础上多了边数的限制，求：从起点S到终点E恰好经过N条边（可以重复经过）的最短路。

回忆一下，floyd是每次用a->b,b->c去更新a->c,以此类推就可以更新出所有点之间的最短路，但无法记录边数，因为每次更新的是自身数组，更新的过程中没有记录，不可查询之前的记录。

这里用类folyd的做法，用矩阵相乘，每次定义一个tenp数组，每次用两个矩阵(图的两个状态a,b)相乘去更新temp，然后再将当前temp的值复制给ans， ans[i][j]即表示从i到j恰好经过n条边的最短路。因为每次更新的是temp，而a就是上一次更新的结果，这样我们更新出a->c这个结