牛站

dp 快速幂 floyd T4

345. 牛站 - AcWing题库

给定一张由 $T$ 条边构成的无向图，点的编号为 $1\sim 1000$ 之间的整数。

求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边（可以重复经过）的最短路。

注意: 数据保证一定有解。

输入格式

第 $1$ 行：包含四个整数 $N，T，S，E$。

第 $\mathrm{2..}T+1$ 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

输出格式

输出一个整数，表示最短路的长度。

数据范围

$2\le T\le 100$,
$2\le N\le 10^6$

输入样例：

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例：

10

思路

先看数据范围, 只有100条边, 也就是说最多也就用200个点, 可以离散化一下。这样的点数说明可以使用floyd算法。

求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边（可以重复经过）的最短路。 可以初步定义状态为：$f(n,i,j)$ 从 $i$ 到 $j$ 经过 $n$ 条边的最短路径 仿照floyd的更新思路, 枚举另外一个点 $k$ ： $f(n,i,j)=min\{f(a,i,k)+f(b,k,j)\}$ , 其中 $a+b=n$ 且均为正整数。那是不是要枚举6层循环？肯定会超时的。

假设这是其中一个正确答案 可以发现 $f(1,S,X_1)$ 和 $f(1,X_1,X_2)$ 之间并没有影响, 更新其中一个不会影响到另一个的取值。计算 $f(2,S,X_2)$ 可以由 $f(1,S,X_1)$ 和 $f(1,X_1,X_2)$ 转移过来, 而之后计算更多的边数时, 可以直接使用 $f(2,S,X_2)$ 代替两个小的状态。也就是说, 在计算结果 $f(7,S,E)$ 时, 用 $f(3,S,X_3)+f(4,X_3,E)$ 和用 $f(4,S,X_4)+f(3,X_4,E)$ 是等价的, 即满足结合律。

那么我们就可以联想到快速幂算法, 用$\log N$ 的复杂度逼近最终边长, 假如答案边长是 $8$, 那我们只需要计算 $1,2,4$ 边长时, 所有点组合的最短路径, 即 $f(1|2|4,i,j)$, 然后把边长相加, 就可以得到最终结果。这个过程是和快速幂非常相似的。

用 $res[i][j]$ 表示答案, $g[k][i][j]$ 表示已经计算出来的算子, 根据快速幂的特性, 每次只需要用到当前长度的值, 下一次也只需要用当前长度的值的平方, 故不需要记录每个长度的情况, 删去 $k$ 所在一维即可。即 $g[i][j]$。

这里就“重载”一下其中的乘法即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <unordered_map>
using namespace std;
const int N = 210;
unordered_map<int,int> ids;
int k,m,S,E,n = 1;
int res[N][N], g[N][N];
 
void mul(int c[][N], int a[][N], int b[][N])
{
    static int temp[N][N];
    memset(temp, 0x3f, sizeof temp);
    for(int k = 1; k < n; k++)
        for(int i = 1; i < n; i++)
            for(int j = 1; j < n; j++)
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
    memcpy(c, temp, sizeof temp);
}
 
void qmi()
{
    memset(res, 0x3f, sizeof res);
    for(int i = 0; i <= n; i++) res[i][i] = 0;
    while(k)
    {
        if(k & 1) mul(res, res, g);
        mul(g, g, g);
        k >>= 1;
    }
}
 
int main()
{
    cin >> k >> m >> S >> E;
    ids[S] = n++;
    ids[E] = n++;
    S = ids[S];
    E = ids[E];
    
    memset(g, 0x3f, sizeof g);
    while(m--)
    {
        int a,b,c;
        cin >> c >> a >> b;
        if(!ids.count(a)) ids[a] = n++;
        if(!ids.count(b)) ids[b] = n++;
        a = ids[a], b = ids[b];
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    qmi();
    
    cout << res[S][E];
    
    return 0;
}