变量含义说明:$k$:输入的 $N$,$m$:输入的 $T$,$st$:输入的 $S$,$ed$:输入的 $E$
离散化
题目中说“点的编号为 $1 \sim 1000$ 之间的整数”,但是实际上用到的点的编号最多只有 $2 \times m + 2$ 个(加上 $st$ 和 $ed$,最坏情况下有 $2 \times 100 + 2 = 202$ 个点),所以我们要做一遍 离散化
才能使得数据范围支持Floyd
的立方级别复杂度
变化Floyd
算法状态
普通Floyd
算法原始状态:
- $d_{k, i, j}$ 代表从点 $i$ 到点 $j$,经过的点的编号在 $1 \sim k$ 的情况下的最短路。
为了符合题目要求,我们将上述状态修改为:
- $d_{k, i, j}$ 代表从点 $i$ 到点 $j$,经过 $k$ 的情况下的最短路。
Floyd
算法转移
我们假设要求出 $d_{a + b, i, j}$ 的值,那么我们可以枚举中间点 $k \in [1, n]$,容易发现,$i$ 到 $k$ 之间选 $a$ 条边与 $k$ 到 $j$ 之间选 $b$ 条边 在选法限制的角度上来讲毫无冲突,所以我们就可以用 $d_{a, i, k} + d_{b, k, j}$ 的值来更新 $d_{a + b, i, j}$ 的值,写出表达式就是 $d_{a + b, i, j} = \min\lbrace d_{a, i, k} + d_{b, k, j} \rbrace \ (k \in [1, n])$。
Floyd
算法转移优化
具体方法见下述代码中mul
函数的实现。
分析出该算法可以用快速幂
解决
假设最终的最短路径为 $st \rightarrow x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow \dots \rightarrow x_{n - 1} \rightarrow ed$,那么 $st \rightarrow x_1$、$x_1 \rightarrow x_2$、$x_2 \rightarrow x_3$、$\dots$、$x_{n - 1} \rightarrow ed$ 这些边相互之间的选择毫无冲突,进而就可以得到边从左往右选、从右往左选、从中间往外选都是可以的,也就是说 “选边”这个过程是具备结合律的,所以就可以用 快速幂
解决。
其他细节见代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, INF_BIT = 0x3f;
const int N = 210;
int k, m, st, ed;
int w, u, v;
unordered_map<int, int> ma;
int n;
//离散化过程
void disc(unordered_map<int, int> &ma, int &n, int &x){
if(!ma.count(x)) ma[x] = ++n;
x = ma[x];
}
int g[N][N];
int t[N][N];
//c = a * b
void mul(int c[N][N], int a[N][N], int b[N][N]){
//更新不影响原数组,可以实现翻倍更新
//此处需要一个临时数组是因为防止更新时发生冲突
memset(t, INF_BIT, sizeof(t));
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
t[i][j] = min(t[i][j], a[i][k] + b[k][j]);
}
}
}
memcpy(c, t, sizeof(t));
}
int ans[N][N];
void ksm(){
memset(ans, INF_BIT, sizeof(ans));
//但是此处i到i之间应该有边
//原因:如果st等于ed,应该输出0
for(int i = 1;i <= n;i++){
ans[i][i] = 0;
}
while(k){
if(k % 2) mul(ans, ans, g);
mul(g, g, g);
k /= 2;
}
}
int main(){
scanf("%d%d%d%d", &k, &m, &st, &ed);
//i到i之间不应该有边
memset(g, INF_BIT, sizeof(g));
disc(ma, n, st);
disc(ma, n, ed);
for(int i = 1;i <= m;i++){
scanf("%d%d%d", &w, &u, &v);
disc(ma, n, u);
disc(ma, n, v);
//建双向边,判断重边
g[u][v] = g[v][u] = min(g[u][v], w);
}
ksm();
printf("%d\n", ans[st][ed]);
return 0;
}