[POJ3613] Cow Relays

link

题目大意

给你一个含有边权的无向图，问从$S$到$T$经过$N$条边的最小花费。

试题分析

我们可以很容易推导$dp$方程,$dp(k,i,j)$表示经过$k$条边从$i$到$j$的最小花费。则，$dp(k,i,j)=min(dp(k-1,i,p)+dp(1,p,j))$。

而$(i,p),(p,j),(i,j)$发现了什么，这不是矩阵吗，$dp(1,i,j)$为初始矩阵($1$次幂),$dp(2,i,j)$为$2$次幂，$dp(3,i,j)$为$3$次幂，所以只需要矩阵快速幂一下即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define int long long

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

struct matrix{

    int st[MAXN][MAXN];

}a,F,ans;

struct node{

    int u,v,w;

}x[MAXN];

int Map[],n,k,m,S,T,cnt;

matrix mul(matrix s1,matrix s2){

    matrix s3;

    memset(s3.st,/,sizeof(s3.st));

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

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

            for(int p=;p<=n;p++){

                s3.st[i][p]=min(s3.st[i][p],s1.st[i][j]+s2.st[j][p]);

            }

    return s3;

}

matrix qpow(int b){

    if(b==) return a;

    ans=a;

    while(b){

        if(b&) ans=mul(ans,a);

        a=mul(a,a);b>>=;

    }return ans;

}

signed main(){

    k=read(),m=read(),S=read(),T=read();

    memset(a.st,/,sizeof(a.st));

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

        int w=read(),u=read(),v=read();

        if(Map[u]==) Map[u]=++cnt;

        if(Map[v]==) Map[v]=++cnt;

        u=Map[u],v=Map[v];

        x[i].w=w,x[i].u=u,x[i].v=v;

        a.st[u][v]=a.st[v][u]=min(a.st[u][v],w);

    }

    n=cnt;

    F=qpow(k-);

    printf("%lld",F.st[Map[S]][Map[T]]);

}

/*

2 3 1 3

1 1 2

1 2 3

1 1 3

*/