见08年论文矩阵乘法。

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]);
}