题解 P2886 【[USACO07NOV]牛继电器Cow Relays】

player · 2018-03-20 15:54:58 · 题解

一道倍增floyd的题。

首先，我们有两个矩阵，如果其中一个矩阵代表恰好经过x条边的最短路，另外一个矩阵代表恰好经过y条边的最短路。那么将这两个矩阵合并就代表恰好经过x+y条边的最短路。怎么合并呢？结合下面这个式子理解一下：

c[i][j]=min(c[i][j],a[i][k]+b[k][j]);

其中i,j,k就是floyd三层循环里的i,j,k ;而a矩阵是经过x条边的最短路，b矩阵是经过y条边的最短路，那么c矩阵就是我们得到的经过x+y条边的最短路了。

那么我们依据初始输入的数组（也就是只经一条边两个点的距离）,这样转移n-1次，就可以得出我们想要的答案了；

然而

这样显然会炸啊！那怎么办呢？我们可以借助类似快速幂的操作去实现。

另外我们还可以将编号离散化

具体看代码吧

#include <bits/stdc++.h>
using namespace std;
int num[1000005];
int n,s,t,e,tol;
struct map
{
    int a[500][500];
    map operator * (const map &x) const //重载运算符，一会儿要用
    {
        map c;
        memset(c.a,0x3f3f3f3f,sizeof(c.a));//取min，显然置大数
        for(int k=1;k<=tol;k++)
            for(int i=1;i<=tol;i++)
                for(int j=1;j<=tol;j++)
                    c.a[i][j]=min(c.a[i][j],a[i][k]+x.a[k][j]);
        return c;       
    }
}dis,ans;
void init()
{
    memset(dis.a,0x3f3f3f3f,sizeof(dis.a));
    int x,y,z;
    cin>>n>>t>>s>>e;
    for(int i=1;i<=t;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        if(!num[y])  //这里做一个离散化
            num[y]=++tol;
        if(!num[z])
            num[z]=++tol;
        dis.a[num[y]][num[z]]=dis.a[num[z]][num[y]]=x;
    }
}
void doit() //快速幂
{
    n--;
    ans=dis;
    while(n)
    {
        if(n&1)
            ans=ans*dis;
        dis=dis*dis;
        n>>=1;
    }
}
int main()
{
    init();
    doit();
    cout<<ans.a[num[s]][num[e]];
}