K点最短路

在OI中,有一类经典的问题叫做经过K点的最短路径, 解题的思路大致是利用flyod和之前我们学习过的广义矩阵乘法, 矩阵快速幂

1. 分析

对于K点的最短路, 我们可以当作是一个传递闭包进行处理,k一定是可以被分解为是2的 $k_i$ 次方的相加, 如果一个传递闭包的级数为k,另外一个的级数为p,那么将这两个相称得到的就是进行k+p次的闭包

我们可以将最短路同理为闭包, K级就意味着在k个点上的最短路径, k+p则是他们和的点数的最短路径, 对于这个闭包运算的实现, 我们可以使用广义矩阵乘法

2 代码

#include <iostream>
#define N 520
using namespace std;
int dp[N][N], vis[1001000];
int n,t,s,e,cnt;
struct matrix {
    int dis[N][N];
    matrix operator*(const matrix&x) const {
        matrix c;
        memset(c.dis,0x3f,sizeof c.dis);
        for (int k = 1; k <= cnt; k++)
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    c.dis[i][j] = min(c.dis[i][j], dis[i][k] + x.dis[k][j]);
        return c;
    }
}now,ans;
int main() {
    memset(now.dis,0x3f,sizeof(now.dis));
    scanf("%d%d%d%d",&n,&t,&s,&e);
    for (int i = 1;i <= t;i++) {
        int x,y,d;
        scanf("%d%d%d",&d,&x,&y);
        if(!vis[x]) {vis[x] = ++cnt;}
        if(!vis[y]) {vis[y] = ++cnt;}
        now.dis[vis[x]][vis[y]] = now.dis[vis[y]][vis[x]] = d;
    }
    n--;
    ans = now;
    while (n) {
        if(n&1) ans = ans*now;
        now = now*now;
        n >>= 1;
    }
    printf("%d\n",ans.dis[vis[s]][vis[e]]);
}