方法1

用 $n$ 个矩阵来表示，第 $k$ 个矩阵的第 $i$ 行第 $j$ 列表示从节点 $i$ 到节点 $j$，恰好经过 $k$ 条边的最短路。第 $k$ 个矩阵与第 $p$ 个矩阵的“积”，就是第 $k+p$ 个矩阵。

类似于矩阵乘法，但两个数之积的和应变为两个数的和的最小值这里既可以重载运算符，也可以写一个单独的函数。
这样，就可以用矩阵快速幂来实现了。

当然，由于边数很少，但点编号较大，可以离散化一下。于是就完美的 AC 了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
struct node
{
    int sq[105][105];
};
int n,t,s,e;//给定一张 T 条边的无向连通图，求从 S 到 E 经过 N 条边的最短路长度。
int map[105][105];
bool app[1001];
int as[1001];
int cnt=0;
int l[101],u[101],v[101];
node mult(node a,node b)
{
    node ret;
    memset(ret.sq,0x3f,sizeof(ret.sq));
    for(int i=1;i<=cnt;i++)
    for(int j=1;j<=cnt;j++)
    for(int x=1;x<=cnt;x++)
    {
        ret.sq[i][j]=min(ret.sq[i][j],a.sq[i][x]+b.sq[x][j]);
    }
    return ret;
}//"矩阵乘法"
node quick(node x,int y)
{
    if(y==1)return x;
    node ret;
    memset(ret.sq,0,sizeof(ret.sq));
    if(y==0)
    {
        return ret;
    }
    ret=quick(x,y>>1);
    return y%2==1?mult(x,mult(ret,ret)):mult(ret,ret);
}//矩阵快速幂
int main()
{
    cin>>n>>t>>s>>e;
    memset(map,0x3f,sizeof(map));
    for(int i=1;i<=t;i++)
    {
        cin>>l[i]>>u[i]>>v[i];
        app[u[i]]=1;
        app[v[i]]=1;
    }
    for(int i=1;i<=1001;i++)
    {
        if(app[i])as[i]=++cnt;
    }
    for(int i=1;i<=t;i++)
    {
        map[as[u[i]]][as[v[i]]]=l[i];
        map[as[v[i]]][as[u[i]]]=l[i];
    }
    node x;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            x.sq[i][j]=map[i][j];
        }
    }
    x=quick(x,n);
    cout<<x.sq[as[s]][as[e]]<<endl;
    return 0;
}

方法2

倍增+Floyd.不多说，上代码（其实是懒）

(仔细想想会发现，两种方法其实并没有本质区别)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
int n,t,s,e;//给定一张 T 条边的无向连通图，求从 S 到 E 经过 N 条边的最短路长度。
int map[105][105];
bool app[1001];
int as[1001];
int cnt=0;
int l[101],u[101],v[101];
int f[20][101][101],g[101][101],ans[101],nean[101];
int main()
{
    cin>>n>>t>>s>>e;
    memset(map,0x3f,sizeof(map));
    for(int i=1;i<=t;i++)
    {
        cin>>l[i]>>u[i]>>v[i];
        app[u[i]]=1;
        app[v[i]]=1;
    }
    for(int i=1;i<=1001;i++)
    {
        if(app[i])as[i]=++cnt;
    }
    for(int i=1;i<=t;i++)
    {
        map[as[u[i]]][as[v[i]]]=l[i];
        map[as[v[i]]][as[u[i]]]=l[i];
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
            f[0][i][j]=map[i][j];
    for(int _=1;1<<_<=n;_++)
        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=cnt;j++)
                for(int k=1;k<=cnt;k++)
                    f[_][i][j]=min(f[_][i][j],f[_-1][i][k]+f[_-1][k][j]);
    memset(ans,0x3f,sizeof(ans));
    ans[as[s]]=0;
    for(int i=0;n;i++,n>>=1)
    {
        if(!(n&1))continue;
        for(int j=1;j<=cnt;j++)
        {
            nean[j]=INF;
            for(int k=1;k<=cnt;k++)
            {
                nean[j]=min(ans[k]+f[i][j][k],nean[j]);
            }
        }
        for(int j=1;j<=cnt;j++)
        {
            ans[j]=nean[j];
        }
    }
    cout<<ans[as[e]]<<endl;
    return 0;
}