2021.11.03 P2886 [USACO07NOV]Cow Relays G(矩阵+floyed)
阅读原文时间:2023年07月09日阅读:3

[P2886 USACO07NOV]Cow Relays G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意:

给出一张无向连通图,求S到E经过k条边的最短路。

分析:

对于floyed,在第k个点时,任意的i到j之间的最短路已经经过了(k-1)个点。当fa[i] [j]经过了x条边,fb[i] [j]经过了y条边,想要算出经过了x+y条边,只需要按照floyed的算法算出fc[i] [j]=min(fa[i] [k]+fb[k] [j],fc[i] [j]),有些像矩阵乘法的算法,那就开始吧~

注:记得对于矩阵的dis初始化/哭唧唧!

[题解 P2886 【USACO07NOV]牛继电器Cow Relays】 - player 的博客 - 洛谷博客 (luogu.com.cn)

代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;

//#define int long long
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int n,start,endi,m,top;
map<int,int>mapi;
struct matrix{
    int a[510][510];
    matrix operator *(const matrix &b)const{
        matrix c;
        memset(c.a,inf,sizeof(c.a));
        for(int k=1;k<=top;k++)
        for(int i=1;i<=top;i++)
        for(int j=1;j<=top;j++)
        c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[k][j]);
        return c;
    }
}dis,ans;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
inline void ksm(){
    --n;ans=dis;
    while(n){
        if(n&1)ans=ans*dis;
        dis=dis*dis;
        n>>=1;
    }
}

signed main(){
    memset(dis.a,inf,sizeof(dis.a));
    n=read();m=read();start=read();endi=read();
    for(int i=1;i<=m;i++){
        int w,u,v;
        w=read();u=read();v=read();
        if(!mapi[u])mapi[u]=++top;
        if(!mapi[v])mapi[v]=++top;
        u=mapi[u];v=mapi[v];
        dis.a[u][v]=dis.a[v][u]=w;
    }
    ksm();
    cout<<ans.a[mapi[start]][mapi[endi]];
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器