题解 luoguP2886 【[USACO07NOV]牛继电器Cow Relays】

首先发现是一张连通图，而且只有 $100$100条边，那么点也很少

编号是乱的，先进行一波离散化，上 $map$map即可(STL大法好)

离散化后，转化成邻接矩阵，这个矩阵实际上表示的是 $i$i到 $j$j只经过 $1$1条边的最短路矩阵。这时发现，我们要求的答案是一个 $st$st到 $ed$ed且只经过 $n$n条边的最短路矩阵。

考虑如何从小矩阵推向大矩阵：设矩阵 $A$A是一个任意两点经过 $x$x条边的最短路矩阵，设矩阵 $B$B是一个任意两点经过 $y$y条边的最短路矩阵

$A$A $\times$× $B$B得到矩阵 $C$C，那么矩阵 $C$C是一个经过 $(x+y)$(x+y)条边的矩阵

重载乘法，因为矩阵转移时的实质为 $Floyd$Floyd松弛： $C$C( $i,j$i,j) $=$= $min$min $\left(A\right(i,k)+B(k,j\left)\right)$(A(i,k)+B(k,j)) ( $1\&lt;=k\&lt;=n$1<=k<=n)

答案就是初始矩阵的 $k$k次方，矩阵快速幂加速即可

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define oo (1e18)
#define int long long
#define LL unsigned long long
#define hh puts("")
using namespace std;
int k,m,st,ed,cnt=0;
map<int,int> mp;
struct matrix{
    int ma[105][105];
    void init(){memset(ma,0x3f,sizeof(ma));}
}f,ans;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
matrix mul(matrix a,matrix b){
    matrix res;
    res.init();
    for(int kk=1;kk<=cnt;kk++)
        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=cnt;j++)
                res.ma[i][j]=min(res.ma[i][j],a.ma[i][kk]+b.ma[kk][j]);
    return res;
}
void ksm(int p){
    while(p){
        if(p&1) ans=mul(ans,f);
        p>>=1;
        f=mul(f,f);
    }
}
signed main(){
    k=read(),m=read(),st=read(),ed=read();
    f.init(),ans.init();
    for(int i=1;i<=m;i++){
        int v=read();
        int x=read(),y=read();
        if(!mp[x]) mp[x]=++cnt;
        if(!mp[y]) mp[y]=++cnt;
        f.ma[mp[x]][mp[y]]=f.ma[mp[y]][mp[x]]=min(f.ma[mp[x]][mp[y]],v);
    }
    for(int i=1;i<=cnt;i++) ans.ma[i][i]=0;
    ksm(k);
    printf("%lld",ans.ma[mp[st]][mp[ed]]);
    return 0;
}