题目大意

给出一张无向连通图（点数小于1000），求S到E经过k条边的最短路。

算法

这是之前国庆模拟赛的题

因为懒所以就只挑一些题写博客

在考场上写了个dp 然后水到了50分出考场和神仙们一问才知道是lyd蓝书原题

我们考虑有两个floyd的矩阵 A代表走了x条边的矩阵 B代表走了y条边的矩阵

那么我们想求出C这个代表走了（x + y）这个矩阵的值呢

我们考虑这么一个式子

\(C[i][j] = min( A[i][k] + B[k][j] )\)

然后我们发现其中\(A[i][k] + B[k][j]\)这个式子和矩阵乘的式子很像

我们把矩阵乘的 \(+\) 改成 \(min\) 即可

那么我们可以考虑将初始给定A矩阵（也就是走了一次的floyd矩阵）进行n - 1次转移

\(A_n[i][j] = (A[i][j]) ^ {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]];

}

巴特西

[USACO07NOV]Cow Relays G

题目大意

算法

代码

最新文章

热门文章