Cow Relays,过N条边的最短路

题目链接

题意：

　　找从a到b的经过N条边的最短路

分析：

　　有点板子。。。方法：矩阵存，然后有个类似快速幂的思想，然后再加上离散化就好了。

　　没啥写的，只能说说矩阵了，我用的方法是先枚举i，j再枚举k，当然大部分人还是喜欢用floyd的代码去写，其实是类似的，然后还有什么呢，就是注意初始化，然后稍微处理一下就好了，代码如下：

　　

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

const int maxn=+;

const int maxm=+;

int ed[maxm][maxm];

int n;

struct JZ{//矩阵

    int a[maxm][maxm];

    JZ(){

        memset(a,0x3f,sizeof(a));

    }

    JZ(int s){

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

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

                a[i][j]=ed[i][j];

    }

    friend JZ operator + (JZ a,JZ b){

        JZ c;

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

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

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

                    c.a[i][j]=min(b.a[i][k]+a.a[k][j],c.a[i][j]);

        return c;

    }

};

int ha[maxn];

int main(){

    memset(ed,0x3f,sizeof(ed));

    int N,m,s,e;

    scanf("%d%d%d%d",&N,&m,&s,&e);

    int js1,js2,js3;

    int js=;

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

        scanf("%d%d%d",&js3,&js1,&js2);

        if(!ha[js1]){

            js++;

            ha[js1]=js;

        }

        if(!ha[js2]){

            js++;

            ha[js2]=js;

        }

        ed[ha[js1]][ha[js2]]=ed[ha[js2]][ha[js1]]=min(ed[ha[js1]][ha[js2]],js3);

    }

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

        if(ha[i])

            n++;

    bool f=;

    JZ D;

    for(JZ now();N;now=now+now){//有点类似快速幂的思想

        if(N&&&f){

            D=now;

            f=;

        }

        else if(N&)

            D=D+now;

        N>>=;

    }

    printf("%d",D.a[ha[s]][ha[e]]);

    return ;

}