【图论】USACO07NOV Cow Relays G

题目大意

洛谷链接

给定一张\(T\)条边的无向连通图，求从\(S\)到\(E\)经过\(N\)条边的最短路长度。

输入格式

第一行四个正整数\(N,T,S,E\)，意义如题面所示。

接下来\(T\)行每行三个正整数\(w,u,v\)分别表示路径的长度，起点和终点。

输出格式

一行一个整数表示图中从\(S\)到\(E\)经过\(N\)条边的最短路长度。

数据范围

对于所有的数据，保证\(1\le N\le 10^6，2\le T\le 100\)。

所有的边保证\(1\le u,v\le 10001，1\le w\le 1000\)。

样例输入

2 6 6 4

11 4 6

4 4 8

8 4 9

6 6 8

2 6 9

3 8 9

样例输出

10

思路

假设有两个矩阵，一个代表恰好经过\(x\)条边的最短路，另外一个代表恰好经过\(y\)条边的最短路。只要把两个矩阵合就可以了。

\(c[i][j]=a[i][k]+b[k][j]\)；

其实还是Floyd。

代码

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

int num[1000005];

int n,s,t,e,tot;

struct map{

    int a[500][500];

    map operator * (const map &x) const{

        map c;

        memset(c.a,0x3f,sizeof(c.a));

        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[i][k]+x.a[k][j]);

        return c;

    }

}dis,ans;

void init(){

    memset(dis.a,0x3f,sizeof(dis.a));

    int x,y,z;

    scanf("%d%d%d%d",&n,&t,&s,&e);

    for(int i=1;i<=t;i++){

        scanf("%d%d%d",&x,&y,&z);//离散化

        if(!num[y])

            num[y]=++tot;

        if(!num[z])

            num[z]=++tot;

        dis.a[num[y]][num[z]]=dis.a[num[z]][num[y]]=x;

    }

}

void work(){//矩阵快速幂

    n--;

    ans=dis;

    while(n){

        if(n&1)

            ans=ans*dis;

        dis=dis*dis;

        n>>=1;

    }

}

int main(){

    init();

    work();

    printf("%d",ans.a[num[s]][num[e]]);

    cout<<ans.a[num[s]][num[e]];

}

巴特西