记录编号	376617	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 奶牛接力	最终得分	100
用户昵称	confoo	是否通过	通过
代码语言	C++	运行时间	0.192 s
提交时间	2017-02-27 18:31:28	内存使用	0.80 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define file(x) "relays." #x
const int N = 210;
int n, m, a, b, f[N][N], t[N][N], l, li[1010];
void mul(int a[N][N], int b[N][N]) {
	static int c[N][N];
	memset(c, 0x3f, sizeof(c));
	for (int i = 1; i <= l; i++) for (int j = 1; j <= l; j++) for (int k = 1; k <= l; k++)
		c[i][j] = std::min(c[i][j], a[i][k] + b[k][j]);
	for (int i = 1; i <= l; i++) for (int j = 1; j <= l; j++) a[i][j] = c[i][j];
}
inline void lisan(int& x) {
	if (!li[x]) li[x] = ++l;
	x = li[x];
}
void print() {
	static int rev[1010];
	for (int i = 1; i <= 1000; i++) rev[li[i]] = i;
	for (int i = 1; i <= l; i++) for (int j = 1; j <= l; j++) if (t[i][j] != 0x3f3f3f3f) printf("%d,%d = %d\n", rev[i], rev[j], t[i][j]);
	puts("");
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d%d%d%d", &n, &m, &a, &b);
	lisan(a), lisan(b);
	memset(f, 0x3f, sizeof(f));
	while (m--) {
		int u, v, w;scanf("%d%d%d", &w, &u, &v);
		lisan(u), lisan(v);
		f[v][u] = f[u][v] = std::min(f[u][v], w);
	}
	memcpy(t, f, sizeof(t));
	n--;
	while (n) {
//		print();
		if (n&1) mul(t, f);
		n >>= 1, mul(f, f);
	}
	printf("%d\n", t[a][b]);
}