最短路 + 矩阵快速幂
我们可以改进矩阵快速幂,使得它适合本题
用图的邻接矩阵和快速幂实现
注意 dis[i][i] 不能置为 0
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
struct edge{
int u, v, dis;
}e[10000];
int n, m, p, ss, tt;
void work() {
int sub[10005];
for(int i = 1; i <= m; i++) {
cin >> e[i].dis >> e[i].u >> e[i].v;
sub[++n] = e[i].u;
sub[++n] = e[i].v;
}
sort(sub + 1, sub + n + 1);
n = unique(sub + 1, sub + n + 1) - sub - 1;
for(int i = 1; i <= m; i++) {
e[i].u = lower_bound(sub + 1, sub + n + 1, e[i].u) - sub;
e[i].v = lower_bound(sub + 1, sub + n + 1, e[i].v) - sub;
}
ss = lower_bound(sub + 1, sub + n + 1, ss) - sub;
tt = lower_bound(sub + 1, sub + n + 1, tt) - sub;
}
struct Matrix{
int num[205][205];
void clear() {
memset(num, 0x3f, sizeof(num));
}
void unit() {
memset(num, 0, sizeof(num));
for(int i = 0; i < 205; i++) num[i][i] = 1;
}
Matrix operator * (const Matrix & b) {
Matrix ans;
ans.clear();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= n; k++) {
ans.num[i][j] = min(ans.num[i][j], num[i][k] + b.num[k][j]);
}
}
}
return ans;
}
void print() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
printf("%d ", num[i][j]);
}
printf("\n");
}
}
Matrix operator ^ (int k) {
Matrix ans;
k--;
ans = (*this);
while(k) {
if(k & 1) ans = ans * (*this);
(*this) = (*this) * (*this);
k >>= 1;
}
return ans;
}
};
int main() {
cin >> p >> m >> ss >> tt;
work();
Matrix a;
a.clear();
//for(int i = 1; i <= n; i++) a.num[i][i] = 0;
for(int i = 1; i <= m; i++) {
a.num[e[i].u][e[i].v] = a.num[e[i].v][e[i].u] = min(e[i].dis, a.num[e[i].u][e[i].v]);
}
a = a ^ p;
//a.print();
printf("%d\n", a.num[ss][tt]);
return 0;
}