[USACO07NOV]Cow Relays

map+floyed+矩阵乘法（倍增floyed）

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <map>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;

IL ll Read(){
    RG char c = getchar(); RG ll x = 0, z = 1;
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
    return x * z;
}

map <int, int> M;
int n, m, k, s, t;
struct Matrix{
    int a[210][210];
    IL void Clear(){  Fill(a, 63);  }
    IL int* operator [](RG int x){  return a[x];  }
    IL Matrix operator *(RG Matrix &B){
        RG Matrix C; C.Clear();
        for(RG int i = 1; i <= n; i++)
            for(RG int j = 1; j <= n; j++)
                for(RG int k = 1; k <= n; k++)
                    C[i][k] = min(C[i][k], a[i][j] + B[j][k]);
        return C;
    }
} ans, edge;

int main(RG int argc, RG char* argv[]){
    edge.Clear(); ans.Clear();
    k = Read(); m = Read(); s = Read(); t = Read();
    if(!M[s]) s = M[s] = ++n; if(!M[t]) t = M[t] = ++n;
    while(m--){
        RG int w = Read(), u = Read(), v = Read();
        if(!M[u]) M[u] = ++n; if(!M[v]) M[v] = ++n;
        edge[M[u]][M[v]] = edge[M[v]][M[u]] = min(edge[M[u]][M[v]], w);
    }
    for(RG int i = 1; i <= n; i++) ans[i][i] = 0;
    while(k){
        if(k & 1) ans = ans * edge;
        edge = edge * edge;
        k >>= 1;
    }
    printf("%d
", ans[s][t]);
    return 0;
}