邻接矩阵乘法两则

USACO 奶牛接力

dp中涉及转移可以用邻接矩阵？
我还是迷迷糊糊不太会扩展。

//奶牛接力
#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];
}
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);
	}
	memset(t, 0x3f, sizeof(t));
	for (int i = 1; i <= l; i++) t[i][i] = 0;
	while (n) {
		if (n&1) mul(t, f);
		n >>= 1, mul(f, f);
	}
	printf("%d\n", t[a][b]);
}

SCOI2009 迷路

大家都会做边权为1。
然后这个问题也可以转化为边权为1。
我一开始把一个带权边拆成许多边权为1的边，可惜会超时。
然后这个题正解是看这个博客的图

//SCOI2009 迷路
#include <cstdio>
#include <cstring>
const int N = 1010, M = 2009;
int n, t, r[N][N], f[N][N], tot;
char buf[30];
void mul(int a[N][N], int b[N][N]) {
	static int c[N][N];
	memset(c, 0, sizeof(c));
	for (int i = 1; i <= tot; i++) for (int j = 1; j <= tot; j++) for (int k=1; k<=tot; k++)
		c[i][k] = (c[i][k] + a[i][j]*b[j][k])%M;
	memcpy(a, c, sizeof(c));
}
int main(){
//	freopen("input", "r", stdin);
	scanf("%d%d", &n, &t);
	tot = n*9;
	for (int i = 1; i <= n; i++) {
		scanf("%s", buf + 1);
		for (int j = 1; j <= n; j++) {
			int l = buf[j] - '0';
			f[i + (l - 1)*n][j] = 1;
		}
	}
	for (int i = 1; i <= n; i++) for (int l = 1; l < 9; l++) f[i + (l-1)*n][i + l*n] = 1;
	for (int i = 1; i <= tot; i++) r[i][i] = 1;
	while (t) {
		if (t&1) mul(r, f);
		t>>=1, mul(f, f);
	}
	printf("%d\n", r[1][n]);
}