【题目链接】

             点击打开链接

【算法】

           朴素算法，就是跑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 = ; i <= tot; i++)

    {

        for (j = ; j <= tot; j++)

        {

                ans.mat[i][j] = INF;

        }

    }

    for (i = ; i <= tot; i++)

    {

        for (j = ; j <= tot; j++)

        {

            for (k = ; 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 > )

    {

        if (n & ) multipy(ans,p);

        n >>= ;

        multipy(p,p);

    }

    a = ans;

}

int main()

{

    for (i = ; i < MAXP; i++)

    {

        for (j = ; j < MAXP; j++)

        {

            ans.mat[i][j] = INF;

        }

    }

    scanf("%d%d%d%d",&N,&T,&S,&E);

    for (i = ; 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\n",ans.mat[h[S]][h[E]]);

    return ;

}