POJ 3613 Cow Relays (Floyd+倍增思想)

題目大意：求經過N條邊的最短路。

好題，更深刻的了解了Floyd和圖鄰接矩陣上的乘法。

這個問題和求兩點間經過N條邊的路徑數很相似，而我們知道如果用圖的鄰接矩陣A存儲圖的話，二分矩陣快速幂A^N即為所求。路徑數能用矩陣乘法求是因為它的狀态方程正好和矩陣乘法一樣：設dp[i][j][p]表示i到j點經過p條邊的路徑數，則dp[i][j][p] = sigma(dp[i][k][p-1]*dp[k][j][1])，即A=B*C（把dp[p]看成A，dp[p-1]看成B……）；

但顯然最短路的方程不是這樣的。按照Floyd的方程它應該是dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])。

那這樣的方程能用類似上面的方法求麼？答案是肯定的，隻要修改一下“乘法”即可。顯然，隻要矩陣運算符合結合律，那麼它就能用二分矩陣快速幂做。關于上面Floyd方程符合結合率的證明，俞華程的論文《矩陣乘法在資訊學中的應用》有證明，不過他前面的我沒看懂。。。

那麼隻要我們重新定義下矩陣“乘法”為：C[i][j] = min(C[i][j], A[i][k]+B[k][j])，問題迎刃而解。

假如我們設圖的鄰接矩陣為VE，則按上面的定義，VE * VE 顯然就是兩點到達經過兩條邊所需要的最短路徑。然後同理VE ^ N就是到達經過N條邊所需要的最短路徑。為什麼這個很類似Floyd的式子求出來的是确定了經過邊數的最短距離？因為這個更新和Floyd不同的是更新到一個新的矩陣上去了而不是直接像Floyd的自己更新自己。是以在一更新時，不會出現自己剛更新的值又來繼續更新。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long LL;
const int sup = 0x7fffffff;
const int inf = -0x7fffffff;

int hash[1000003], cnt;
struct mat{
    long long map[200][200];
    void init(){
        mem(map, -1);
    }
    void make_head(){
        mem(map, -1);
        for (int i = 0; i < cnt; i ++)
            map[i][i] = 0;
    }
}A;
int n, t, s, e;
mat floyd(mat &A, mat &B){
    mat res;
    res.init();
    for (int k = 0; k < cnt; k ++){
        for (int i = 0; i < cnt; i ++){
            if (A.map[i][k] != -1){
                for (int j = 0; j < cnt; j ++){
                    if(B.map[k][j] != -1){
                        if (res.map[i][j] == -1){
                            res.map[i][j] = A.map[i][k] + B.map[k][j];
                        }
                        else{
                            res.map[i][j] = min(res.map[i][j], A.map[i][k] + B.map[k][j]);
                        }
                    }
                }
            }
        }
    }
    return res;
}
long long work(mat &A, int n){
    mat res;
    res.make_head();
    while(n){
        if (n & 1){
            res = floyd(res, A);
        }
        n >>= 1;
        A = floyd(A, A);
    }
    return res.map[hash[s]][hash[e]];
}
int main(){
    mem(hash, -1);
    A.init();
    cnt = 0;
    scanf("%d %d %d %d", &n, &t, &s, &e);
    if (hash[s] == -1)
        hash[s] = cnt ++;
    if (hash[e] == -1)
        hash[e] = cnt ++;
    for (int i = 0; i < t; i ++){
        int l, a, b;
        scanf("%d %d %d", &l, &a, &b);
        if (hash[a] == -1)
            hash[a] = cnt ++;
        if (hash[b] == -1)
            hash[b] = cnt ++;
        A.map[hash[a]][hash[b]] = l;
        A.map[hash[b]][hash[a]] = l;
    }
    printf("%I64d\n", work(A, n));
	return 0;
}
      

舉杯獨醉，飲罷飛雪，茫然又一年歲。 ------AbandonZHANG