洛谷 [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("%d\n", a.num[ss][tt]);

	return 0;

}

巴特西

洛谷 [P2886] 牛继电器Cow Relays

最短路 + 矩阵快速幂

最新文章

热门文章