P2886 [USACO07NOV]Cow Relays G 题解(矩阵快速幂 floyd)

题目链接

题目大意

求\(s\)到\(e\)中，恰好经过\(n\)条边的最短路

题目思路

看到经过\(n\)条边，就要想到矩阵快速幂的思想

然后是最短路，利用floyd的思想，不是普通的floyd的稍微有些变化，但是思想是一样的

每一次floyd相当于多走了一条边

还需要离散化

代码

#include
#include
#include
#define fi first
#define se second
#define pii pair
#define debug cout<<"I AM HERE"<>1;
    }
}
signed main(){
    memset(base.a,0x3f,sizeof(base.a));
    scanf("%d%d%d%d",&n,&t,&s,&e);
    for(int i=1,u,v,w;i<=t;i++){
        scanf("%d%d%d",&w,&u,&v);
        if(!hs[u]) hs[u]=++cnt;
        if(!hs[v]) hs[v]=++cnt;
        base.a[hs[u]][hs[v]]=base.a[hs[v]][hs[u]]=w;
    }
    ans=base;
    qpow(cnt,n-1);
    printf("%lld\n",ans.a[hs[s]][hs[e]]);
    return 0;
}