Floyd思想和倍增思想

例题：345.牛站

时间复杂度：

  • O(n^3*logm)

算法思路：

  • Floyd思想：
    • 状态表示：d[K][i][j]为从i到j的经过前K条边的路径的最小值(与Floyd的d[n][i][j]经过前n个点的表示方法略有不同)
    • 状态计算：d[K][i][j] = d[a][i][k] + d[b][k][j]，其中k为经过前a条边后的点，
    • 更新一次可以增加两条边，更新两次增加三条边，如此我们仅需更新m-1次即可得到d[m][S][E]，时间复杂度为：O(n^3*m) n为200，m为1e6必定TLE
    • 可以用倍增思想来将时间复杂度化为logm
  • 倍增思想(快速幂思想)
    • 最终路径类似于：S->x1->x2->x3->……->……->xm-1->E, 中间经过了m-1个点，m条边
    • 我们可发现上述的路径先计算与后计算不会相互影响，即可以先计算中间的或先计算后面的，具有结合律，如此可借助倍增思想，仅需logm次即可找到合法路径
    • 时间复杂度：O(n^3*logm)

具体实现：

  • 哈希所有用过的点，包括起点和终点
  • 倍增算法

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int N = 210, M = 1000010;

int n, m, K, S, E;
int g[N][N];
int res[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);
    
    // 一条边都不走，i->i必须为0
    for (int i = 1; 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;
    
    map<int, int> ids;
    
    if (!ids.count(S)) ids[S] = ++ n;
    if (!ids.count(E)) ids[E] = ++ n;
    S = ids[S], E = ids[E];
    
    memset(g, 0x3f, sizeof g);
    
    // 初始化自环为0，即经过一条边走到自身的权值为0，多此一举
    // 因为通过一条边的权值可能大于0，如果初始化为0，则之后的边无法在g中表现出来
    // for (int i = 1; i <= N; i ++ )
    //     g[i][i] = 0;
    
    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] << endl;
    
    return 0;
}