[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;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章