洛谷2886 [USACO07NOV]Cow Relays

题意

给出一张无向连通图，求 $S$ 到 $E$ 经过 $N$ 条边的最短路。

其中边数 $T\le 100$ ，点的编号 $\le 1000$ ，$N\le 10^6$ 。

题解

因为是连通图，所以点最多有 $T+1\le 101$ 个。显然 $O(T^3)$ 的 $\text{Floyd}$ 是可以接受的。

考虑 $\text{Floyd}$ 的过程：

$$\text{dis[i][j]}=\min(\text{dis[i][j]},\text{dis[i][k]}+\text{dis[k][j]})$$

如果 $i\rightarrow k$ 经过 $x$ 条边，$k\rightarrow j$ 经过 $y$ 条边，那么显然更新后的 $i\rightarrow j$ 经过 $x+y$ 条边。

初始的距离关系表示的是 $1$ 条边的最短路，那做 $N-1$ 次操作就可以得到答案了。

但直接做的复杂度是 $O(T^3N)$ ，显然不行，考虑优化。

把二维数组看成矩阵，修改矩阵乘法为类似 $\text{Floyd}$ 的过程：

$$C[i,j]=\min^b_{k=1} (A[i,k]B[k,j])$$

其中 $A$ 是 $a\times b$ 的矩阵，$B$ 是 $b\times c$ 的矩阵，C即为 $a\times c$ 的矩阵。

这个式子仍然是满足结合律的，证明详见 俞华程《矩阵乘法在信息学中的应用》。所以可以用快速幂计算，复杂度为 $O(T^3\log N)$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,t,s,e,cnt,a,b,c,v[1005];
struct matrix {
    int s[105][105];
    matrix() { memset(s,0,sizeof(s)); }
    matrix operator * (const matrix &x) const {
        matrix y;
        memset(y.s,0x3f,sizeof(y.s));
        for (int k=1;k<=cnt;k++)
            for (int i=1;i<=cnt;i++)
                for (int j=1;j<=cnt;j++)
                    y.s[i][j]=min(y.s[i][j],s[i][k]+x.s[k][j]);
        return y;
    }
} dis;

inline void init(matrix &x);
inline matrix qpow(matrix x,int y);
inline void print(matrix x);

signed main()
{
    memset(dis.s,0x3f,sizeof(dis.s));
    n=read(); t=read(); s=read(); e=read();
    for (int i=1;i<=t;i++)
    {
        c=read(); a=read(); b=read();
        if (!v[a]) v[a]=++cnt;
        if (!v[b]) v[b]=++cnt;
        dis.s[v[a]][v[b]]=dis.s[v[b]][v[a]]=min(dis.s[v[a]][v[b]],c);
    }
    print(qpow(dis,n-1));
    return 0;
}

inline void init(matrix &x) { for (int i=1;i<=cnt;i++) x.s[i][i]=1; }

inline matrix qpow(matrix x,int y)
{
    matrix ans=x;
    while (y)
    {
        if (y&1) ans=ans*x;
        y>>=1;
        x=x*x;
    }
    return ans;
}

inline void print(matrix x) { printf("%d",x.s[v[s]][v[e]]); }