Cow Relays,过N条边的最短路

题目链接

题意：

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

分析：

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

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

　　

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000+10;
const int maxm=200+10;
int ed[maxm][maxm];
int n;
struct JZ{//矩阵
    int a[maxm][maxm];
    JZ(){
        memset(a,0x3f,sizeof(a));
    }
    JZ(int s){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=ed[i][j];
    }
    friend JZ operator + (JZ a,JZ b){
        JZ c;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;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=0;
    for(int i=1;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=1;i<maxn;i++)
        if(ha[i])
            n++;
    bool f=1;
    JZ D;
    for(JZ now(1);N;now=now+now){//有点类似快速幂的思想
        if(N&1&&f){
            D=now;
            f=0;
        }
        else if(N&1)
            D=D+now;
        N>>=1;
    }
    printf("%d",D.a[ha[s]][ha[e]]);
    return 0;
}