从点S到E刚好经过N条边的最短路径

题目地址：https://ac.nowcoder.com/acm/contest/1055/G
《算法进阶》P362

①关于min的矩阵乘法：https://blog.nowcoder.net/n/09c63cb41aba4ab5bf67450b243e0eba
若矩阵 保存任意两点之间恰好经过m条边的最短路，则：

相当于增加一个中转点就增加一条边

②矩阵快速幂
本来两个二维数组不能直接相乘，但重载运算符后，直接按照矩阵乘法规律相乘，方便许多

总时间复杂度O (T^3 log N)

#include<bits/stdc++.h>
using namespace std;
const int maxn=10*100+10;
int Hash[maxn];//Hash数组代表点离散化后的对应点，其实就是按照输入依次把点加进去 
int to=0,n,t,S,E;
struct Matrix
{
    int a[maxn][maxn];
    Matrix operator * (const Matrix &x) const//重载运算符 
    {
        Matrix c;
        memset(c.a,0x3f,sizeof(c.a));
        for(int k=1;k<=to;k++)//floyd求任意两点最短路径 
        {
            for(int i=1;i<=to;i++)
            {
                for(int j=1;j<=to;j++)
                {
                    c.a[i][j] = min(c.a[i][j],a[i][k]+x.a[k][j]);
                }
            }
        }
        return c;
    }
}s1,ans;
void ksm()//矩阵快速幂 
{
    ans=s1;
    n--;
    for(;n;n>>=1)
    {
        if(n&1==1)
        {
            ans=ans*s1;
        }
        s1=s1*s1;
    }
}
int main()
{
    cin>>n>>t>>S>>E;
    memset(s1.a,0x3f,sizeof(s1.a));
    for(int i=1;i<=t;i++)
    {
        int u,v,w;
        cin>>w>>u>>v;
        if(!Hash[u])    Hash[u]=++to;//如果未被标记才把点加进去 
        if(!Hash[v])    Hash[v]=++to;
        s1.a[Hash[u]][Hash[v]]=s1.a[Hash[v]][Hash[u]]=w;
    }
    ksm();
    cout<<ans.a[Hash[S]][Hash[E]]<<endl;
    return 0;
}

来源：https://www.cnblogs.com/mjtcn/p/7308870.html