想要更好的阅读体验？

T3

相比于T2,其实这题更套路.
首先$n\le 100$暗示Floyd,先求出$dis^0(i,j)$表示$i->j$不用魔法的最短距离
设$dis^k(i,j)$表示$i->j$恰用$k$次魔法的最短距离 (由于所有边权非负,$dis^k(i,j)$关于$k$单调递减所以$dis^k(1,n)$即为答案,求出它即可.)

若已知$dis^{k-1},dis^1$,则
$$dis^k(i,j)=\min_{1\le p\le n} \lbrace dis^{k-1}(i,p)+dis^1(p,j) \rbrace$$
一个广义矩阵乘法的形式,如果知道了$dis^1,$直接矩阵快速幂就好,时间复杂度$\mathcal O(n^3\log K)$
求$dis^1$也简单,枚举每条边$(u,v,w)$做为变成负权的那条边,那么$dis^1(s,t)=dis^0(s,u)-w+dis^0(v,t)$,时间复杂度$\mathcal O(n^2m)$

总时间复杂度$\mathcal O(n^3\log K+n^2m)$

/**********/
#define MAXN 111
#define MAXM 2511
ll n;
struct mat
{
    ll a[MAXN][MAXN];
    mat(ll t[MAXN][MAXN])
    {
        for(ll i=1;i<=n;++i)
            for(ll j=1;j<=n;++j)a[i][j]=t[i][j];
    }
    mat(){}
    mat operator *(const mat& t)//广义矩阵乘法
    {
        ll sum[MAXN][MAXN];
        for(ll i=1;i<=n;++i)
            for(ll j=1;j<=n;++j)
            {
                sum[i][j]=a[i][1]+t.a[1][j];
                for(ll k=2;k<=n;++k)
                    umin(sum[i][j],a[i][k]+t.a[k][j]);
            }
        return mat(sum);
    }
    mat Qpow(ll p)//矩阵快速幂,求a^p
    {
        --p;
        mat res=*this,cur=*this;
        while(p)
        {
            if(p&1)res=res*cur;
            cur=cur*cur;
            p>>=1;
        }
        return res;
    }
}a;//a就是dis1

ll dis[MAXN][MAXN];//dis0
void Floyd(ll n)
{
    for(ll k=1;k<=n;++k)
        for(ll i=1;i<=n;++i)
            for(ll j=1;j<=n;++j)
                umin(dis[i][j],dis[i][k]+dis[k][j]);
}
struct edge
{
    ll u,v,w;
}e[MAXM];
int main()
{
    n=read();
    ll m=read(),k=read();
    memset(dis,0x3f,sizeof dis);
    for(ll i=1;i<=n;++i)dis[i][i]=0;
    a=mat(dis);
    for(ll i=1;i<=m;++i)
    {
        ll u=read(),v=read(),w=read();
        umin(dis[u][v],w);
        e[i]=edge{u,v,w};
    }
    Floyd(n);
    if(k==0)
    {
        printf("%lld",dis[1][n]);
        return 0;
    }
    for(ll i=1;i<=m;++i)
    {
        ll u=e[i].u,v=e[i].v,w=e[i].w;
        for(ll s=1;s<=n;++s)
            for(ll t=1;t<=n;++t)
                umin(a.a[s][t],dis[s][u]-w+dis[v][t]);
    }
    printf("%lld",a.Qpow(k).a[1][n]);
    return 0;
}