[洛谷 2886][USACO07NOV]Cow Relays

题目链接

https://www.luogu.org/problem/P2886

题解

假如 \(f\) 矩阵代表走 \(x\) 条边时的最短路,\(g\) 矩阵代表走 \(y\) 条边的最短路,那么可以根据 floyd 算法,按如下规则构造 \(h\) 矩阵,代表走 \(x+y\) 条边时的最短路:

$$h_{i,j}=min\{h_{i,j},f_{i,k}+g_{k,j}\}$$

容易看出这个可以用矩阵快速幂优化计算。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct mat
{
 long long a[205][205];
 mat(int x=0)
 {
  memset(a,x,sizeof(a));
 }
}f(63),ans(63);
int tot,m[1005];
mat operator*(mat a,mat b)
{
 mat c(63);
 for(int k=1;k<=tot;k++)
  for(int i=1;i<=tot;i++)
   for(int j=1;j<=tot;j++)
    c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
 return c;
}
int main()
{
 int n,t,s,e;
 cin>>n>>t>>s>>e;
 for(int i=1;i<=t;i++)
 {
  int w,u,v;
  cin>>w>>u>>v;
  if(!m[u])m[u]=++tot;
  if(!m[v])m[v]=++tot;
  f.a[m[u]][m[v]]=f.a[m[v]][m[u]]=w;
 }
 for(int i=1;i<=tot;i++)
  ans.a[i][i]=0;
 while(n)
 {
  if(n&1)ans=ans*f;
  f=f*f;
  n>>=1;
 }
 cout<<ans.a[m[s]][m[e]]<<endl;
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据