题目链接：?id=3613题目大意：求从起点s到终点e经过k条边的最短路径题目分析：01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数，而Floyd则是每次使用一个中间点k去更新i,j之间的距离，那么更新成功表示i,j之间恰有一个点k时的最短路，做n – 1次Floyd即是在i，j之间经过n – 1 个点时的最短路，i，，j之间有n－1个点即有n条边，因为n比较大，考虑采用矩阵快速幂来求，还有就是这题的t比较小，但是l1，l2比较大，所以将其离散化，因为t最大为100，所以离散化后最多有200个点#include <cstdio>#include <cstring>int h[205], cnt;struct matrix{int m[205][205];matrix(){memset(m, 0x3f, sizeof(m));}};matrix Floyd(matrix a, matrix b) {matrix ans;for(int k = 1; k <= cnt; k++)for(int i = 1; i <= cnt; i++)for(int j = 1; j <= cnt; j++)if(ans.m[i][j] > a.m[i][k] + b.m[k][j])ans.m[i][j] = a.m[i][k] + b.m[k][j];return ans;}matrix quickmod(matrix a, int k){matrix ans = a;while(k){if(k & 1)ans = Floyd(ans, a);k >>= 1;a = Floyd(a, a);}return ans;}int main(){int n, t, s, e;cnt = 1;matrix ans;scanf("%d %d %d %d", &n, &t, &s, &e);memset(h, 0, sizeof(h));for(int i = 0; i < t; i++){int u, v, w;scanf("%d %d %d", &w, &u, &v);if(!h[u])h[u] = cnt++;if(!h[v])h[v] = cnt++;if(ans.m[h[u]][h[v]] > w)ans.m[h[u]][h[v]] = ans.m[h[v]][h[u]] = w;}ans = quickmod(ans, n – 1);printf("%d\n", ans.m[h[s]][h[e]]);}
征服畏惧、建立自信的最快最确实的方法，
