【题目链接】
【算法】
朴素算法，就是跑N-1遍floyd
而满分算法就是通过矩阵快速幂加速这个过程
【代码】
注意要离散一下
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXP 250 #define MAXC 1010 const int INF = 1e9; int N,T,S,E,i,j,l,u,v,tot; int h[MAXC]; struct Matrix { int mat[MAXP][MAXP]; } ans; inline void multipy(Matrix &a,Matrix b) { int i,j,k; static Matrix ans; for (i = 1; i <= tot; i++) { for (j = 1; j <= tot; j++) { ans.mat[i][j] = INF; } } for (i = 1; i <= tot; i++) { for (j = 1; j <= tot; j++) { for (k = 1; k <= tot; k++) { ans.mat[i][j] = min(ans.mat[i][j],a.mat[i][k]+b.mat[k][j]); } } } a = ans; } inline void power(Matrix &a,int n) { int i,j; static Matrix ans=a,p=a; n--; while (n > 0) { if (n & 1) multipy(ans,p); n >>= 1; multipy(p,p); } a = ans; } int main() { for (i = 1; i < MAXP; i++) { for (j = 1; j < MAXP; j++) { ans.mat[i][j] = INF; } } scanf("%d%d%d%d",&N,&T,&S,&E); for (i = 1; i <= T; i++) { scanf("%d%d%d",&l,&u,&v); if (!h[u]) h[u] = ++tot; if (!h[v]) h[v] = ++tot; ans.mat[h[u]][h[v]]= ans.mat[h[v]][h[u]] = min(ans.mat[h[u]][h[v]],l); } power(ans,N); printf("%d ",ans.mat[h[S]][h[E]]); return 0; }