洛谷 [P2886] 牛继电器Cow Relays

洛谷 [P2886] 牛继电器Cow Relays

最短路 + 矩阵快速幂

我们可以改进矩阵快速幂,使得它适合本题
用图的邻接矩阵和快速幂实现
注意 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("%dn", a.num[ss][tt]);return 0;
}

转载于:.html