$k$ 边最短路-矩乘

\(k\) 边最短路-矩乘

P2886 Cow Relays G
简单模板

题意

给定 \(T\) 条边（\(T \le 100\)），起点 \(s\) 和终点 \(v\)，问 \(s\) 到 \(v\) 经过 \(n\) 条边的最短路长度。

思路

写过几题矩阵乘法的都知道一个 \(01\) 邻接矩阵的方，就成了一个点经过两条边能否到另一个点。我们修改一下，把原本的两个 \(1\) 相乘得到 \(1\) 表示可达，换成最短路的不可达用 \(INF\) 表示，两条边相加取 \(min\) 表示可能的最短路。同样我们发现，$ C[i][j]=A[i][k]+B[k][j]$ 满足矩阵乘法的交换律和分配律，意味着可以进行矩阵快速幂。其他细节看注释。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 1e3 + 10;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;typedef struct mat
{vector<vector<int>> num;int row, col;mat(int r, int c, int x = 0) : row(r), col(c){// 这题的矩阵默认都应该是INF，但我这里是传INFnum.assign(r, vector<int>(c, x));}vector<int> &operator[](const int &x)// vector的[]重载{return num[x];}const vector<int> &operator[](const int &x) const{return num[x];}mat operator*(const mat &x) const{mat ret(row, x.col, INF);for (int i = 0; i < row; ++i){for (int k = 0; k < col; ++k)// 先行后列快一点{int val = num[i][k];for (int j = 0; j < x.col; ++j){ret[i][j] = min(ret[i][j], val + x[k][j]);// 取nin}}}return ret;}mat operator^(int ci) const{if(!ci) return *this;mat ans = *this;// 默认一次，不用构造单位矩阵（这里的单位矩阵是对角线为0，其余为INF）mat base = *this;--ci;while (ci){if (ci & 1) ans = ans * base;base = base * base;ci >>= 1;}return ans;}
} mat;int id[maxn];
mat mp(105, 105, INF);signed main()
{
#ifndef ONLINE_JUDGEfreopen("cjdl.in", "r", stdin);freopen("cjdl.out", "w", stdout);
#endifint n, t, s, e, idx = 0;scanf("%lld%lld%lld%lld", &n, &t, &s, &e);for (int i = 1, w, u, v; i <= t; ++i){scanf("%lld%lld%lld", &w, &u, &v);u = id[u] ? id[u] : id[u] = ++idx;// 映射v = id[v] ? id[v] : id[v] = ++idx;mp[u][v] = mp[v][u] = min(mp[u][v], w);}mp = mp^n;s = id[s];e = id[e];printf("%lld", mp[s][e]);return 0;
}