poj 3613 经过k条边最短路 floyd+矩阵快速幂

http://poj.org/problem?id=3613

s->t上经过k条边的最短路

先把1000范围的点离散化到200中，然后使用最短路可以使用floyd，由于求的是经过k条路的最短路，跑k-1次“floyd”即可(使用矩阵快速幂的思想)。

把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <sstream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define clr1(x) memset(x,-1,sizeof(x))

#define eps 1e-9

const double pi = acos(-1.0);

typedef long long LL;

const int inf = 0x7fffffff;

const int maxn = 205;

map <int , int> mp;

int k,m,st,en;

int n;//floyd矩阵大小

struct Matrix{

    int mat[maxn][maxn];

    void init(){

        for(int i = 0;i < maxn;++i)

            for(int j = 0;j < maxn;++j)

                mat[i][j] = inf;

    }

};

Matrix ans,tmp,_tmp;

void copy(Matrix &b,Matrix a){

    for(int i = 1;i <= n;++i)

        for(int j = 1;j <= n;++j)

            b.mat[i][j] = a.mat[i][j];

}

void floyd(Matrix &a,Matrix b,Matrix c){

    a.init();

    for(int k = 1;k <= n;++k)

    for(int i = 1;i <= n;++i)

    for(int j = 1;j <= n;++j){

        if(b.mat[i][k] == inf || c.mat[k][j] == inf)

            continue;

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

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

    }

}

int has[1005];

void init()

{

    n = 0;

    clr0(has);

    ans.init(),tmp.init();

    for(int i = 0;i < maxn;++i)

        ans.mat[i][i] = 0;

    int u,v,w;

    for(int i = 0;i < m;++i){

        RD3(w,u,v);

        if(has[u] == 0)

            has[u] = ++n;

        if(has[v] == 0)

            has[v] = ++n;

        if(tmp.mat[has[u]][has[v]] > w)

            tmp.mat[has[v]][has[u]] = tmp.mat[has[u]][has[v]] = w;

    }

}

void work()

{

    while(k){

        if(k&1){

            copy(_tmp,ans);

            floyd(ans,_tmp,tmp);

        }

        copy(_tmp,tmp);

        floyd(tmp,_tmp,_tmp);

        k>>=1;

    }

    printf("%d\n",ans.mat[has[st]][has[en]]);

}

int main()

{

    while(~RD2(k,m)){

        RD2(st,en);

        init();

        work();

    }

    return 0;

}