经过N条边的最短路

http://acm.pku.edu.cn/JudgeOnline/problem?id=3613

求经过N条边的最短路 (2 ≤ N ≤ 1,000,000）

倍增floyd，主体是矩阵乘法。考虑一个x边的路径矩阵和y边的路径矩阵，两个矩阵用类似floyd的方法结合起来，就得到x+y边的路径矩阵，现在想要得到N边路径矩阵

然后就是“快速幂”的思想啦...把N拆成2的幂，只需要log(N)次矩阵乘法就搞定

伪floyd O(N^3)，所以总的时间复杂度O(logN*n^3) 其中n是点的个数 由于最多100个边，所以n最大200

虽说只有最多200个点，然而点点序号却很迷的到了1000，所以用了离散化，把点的序号映射到1～200范围

答案矩阵开始时候应该为单位矩阵 在这个倍增floyd定义下 单位矩阵应该是迹为0 其他值为正无穷

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

const int maxn = , INF = 0x3f3f3f3f;

map<int, int>M;

int cnt, n, t, s, e;

struct floyd{

    int a[maxn][maxn];

    floyd(){

        memset(a, INF, sizeof(a));

    }

    floyd operator * (const floyd& b){

        floyd c;

        for(int i = ; i <= cnt; i++)

            for(int j = ; j <= cnt; j++)

                for(int k = ; k <= cnt; k++)

                    if(c.a[i][j] > a[i][k] + b.a[k][j])

                        c.a[i][j] = a[i][k] + b.a[k][j];

        return c;

    }

}st, ans;

void quick(){

   // ans = st;

   // n--;

    while(n){

        if(n&){

            ans = ans*st;

        }

        st = st * st;

        n >>= ;

    }

}

int main(){

    scanf("%d%d%d%d", &n, &t, &s, &e);

    cnt = ;

    while(t--){

        int w, x, y;

        scanf("%d%d%d", &w, &x, &y);

        if(M[x])

            x = M[x];

        else

            x = M[x] = ++cnt;

        if(M[y])

            y = M[y];

        else

            y = M[y] = ++cnt;

        st.a[x][y] = st.a[y][x] = w;

    }

    for(int i = ; i <= cnt; i++)

        ans.a[i][i] = ;

    quick();

    printf("%d", ans.a[M[s]][M[e]]);

    return ;

}