洛谷P2886 [USACO07NOV]Cow Relays G 题解

题目链接：P2886 [USACO07NOV]Cow Relays G

题意：

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

输入格式：

第一行四个正整数 $N,T,S,E$ ，意义如题面所示。

接下来 $T$ 行每行三个正整数 $w,u,v$ ，分别表示路径的长度，起点和终点。

输出格式：

一行一个整数表示图中从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度。

数据范围：

对于所有的数据，保证 $1\le N\le 10^6$，$2\le T\le 100$。

所有的边保证 $1\le u,v\le 1000$，$1\le w\le 1000$，无重边。

这道题考察了无向图邻接矩阵的性质。

如果矩阵 $A$ 表示走了 $x$ 步的最短路，矩阵 $B$ 表示走了 $y$ 步的最短路，

$$C_{i,j} \downarrow A_{i,k} + B_{k,j}$$

矩阵 $C$ 就表示走了 $x+y$ 步的最短路。（cxy：这我懂，不就 Floyd 吗）

这个和 Floyd 的区别在于， $C$ 矩阵初始状态全为 $+\infty$ ，而 Floyd 可能是 $A$ 也可能是 $B$ 。

换句话说，我们强制它多走了几条边，自然不一样。搞清楚这点，这题就想通了。

不要忘了离散化一下节点，而且矩阵快速幂的 $\texttt{Ans}$ 也要改成 $M$ 哦（见代码）

时间复杂度 $\mathcal{O}(T^3\log N)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
typedef vector< vector<int> > mat;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
// void add(int &x,int y) { (x += y) >= mod ? x -= mod : x; }
#define N ((int)())

mat mul(mat A, mat B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    mat C(n, vector<int>(p, 0x7f7f7f7f));
    for(int k = 0; k < m; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < p; j++) down(C[i][j], A[i][k] + B[k][j]);
    return C;
}
mat qpow(mat A, int b)
{
    mat ans = A;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}
int tot = 0, vis[1115];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,m,s,t; cin >> n >> m >> s >> t; --s; --t;
    memset(vis,-1,sizeof(vis)); mat M(m + 1, vector<int>(m + 1, INF));
    for(int i = 0,u,v,w; i < m; i++)
    {
        cin >> w >> u >> v; --u; --v;
        u = (~vis[u]) ? vis[u] : (vis[u] = tot++);
        v = (~vis[v]) ? vis[v] : (vis[v] = tot++);
        M[v][u] = M[u][v] = w;
    }
    mat res = qpow(M, n - 1); cout << res[vis[s]][vis[t]] << '\n';
    return 0;
}

据说这道题有个 $\mathcal{O}(T^2)$ 的贪心做法，有兴趣可以去看这篇题解