发布时间：2024-07-31

矩阵快速幂求解经过n条边的最短路

• 邻接矩阵$A$,$A^n$表示经过$n$条路径的最短路

struct Matrix{
    int m[210][210];
    int x,y;
    Matrix(int _x=0,int _y=0):x(_x),y(_y){memset(m,0x3f,sizeof m);}
    Matrix operator*(const Matrix &t)const{
        Matrix res(x,t.y);
        for(int k=1;k<=y;k++){
            for(int i=1;i<=x;i++){
                for(int j=1;j<=t.y;j++){
                    res.m[i][j]=min(res.m[i][j],m[i][k]+t.m[k][j]);
                }
            }
        }
        return res;
    };
};
Matrix qpow(Matrix a,int b){
    Matrix res(a.x,a.y);
    for(int i=1;i<=a.x;i++)res.m[i][i]=0;
    while(b){
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
void solve(){
    int n,t,s,e;
    cin>>n>>t>>s>>e;
    map<int,int> mp;
    auto get=[&](int x){
        if(mp.count(x))return mp[x];
        return mp[x]=mp.size()+1;
    };
    s=get(s),e=get(e);
    Matrix ans;
    for(int i=1;i<=t;i++){
        int u,v,w;
        cin>>w>>u>>v;
        u=get(u),v=get(v);
        ans.m[u][v]=ans.m[v][u]=min(ans.m[u][v],w);
    }
    ans.x=ans.y=mp.size();
    ans=qpow(ans,n);
    cout<<ans.m[s][e]<<"\n";
}