「POJ3613」Cow Relays

传送门

就一个思想:\(N\) 遍 \(\text{Floyd}\) 求出经过 \(N\) 个点的最短路

看一眼数据范围,想到离散化+矩阵快速幂

代码:

#include <cstring>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

template < class T > inline void chkmin(T& a, const T& b) { if (a > b) a = b; }

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 502, __ = 1e6 + 5;

int n, m, s, t, tot, id[__];

struct Matrix {

	int a[_][_];

	inline void init() { memset(a, 0x3f, sizeof a); }

	inline int* operator [] (const int& id) { return a[id]; }

	inline Matrix operator * (const Matrix& b) const {

		Matrix ans; ans.init();

		for (rg int k = 1; k <= tot; ++k)

			for (rg int i = 1; i <= tot; ++i)

				for (rg int j = 1; j <= tot; ++j)

					chkmin(ans.a[i][j], a[i][k] + b.a[k][j]);

		return ans;

	}

} f;

inline Matrix power(Matrix x, int k) {

	Matrix res = x; --k;

	for (; k; k >>= 1, x = x * x)

		if (k & 1) res = res * x;

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	read(n), read(m), read(s), read(t), f.init();

	for (rg int u, v, w; m--; ) {

		read(w), read(u), read(v);

		if (!id[u]) id[u] = ++tot;

		if (!id[v]) id[v] = ++tot;

		f[id[u]][id[v]] = f[id[v]][id[u]] = w;

	}

	Matrix res = power(f, n);

	printf("%d\n", res[id[s]][id[t]]);

	return 0;

}

巴特西

「POJ3613」Cow Relays

「POJ3613」Cow Relays

最新文章

热门文章