csp赛前刷题篇图论篇 [USACO07NOV]Cow Relays G

https://www.luogu.com.cn/problem/P2886

看一眼本题，Floyd算法。那么什么是Floyd算法呢？？

Floyd

设

代码实现：

	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

下面让我们魔改一下
令f[k，i，j]表示 从i经过k条边到达j 原Floyd表达 从i 到j走1~k个点，最短路径是多少。
魔改后 转移方程 f[a+b,i,j]=min(f[a,i,k],f[b,i,k]),k=1~n。
 $d [a,$ 这个转移方程表示从

sort(sub_a,sub_a+n);

int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数

for(i=0;i<n;i++) a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>

#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;

const int N =  507;

int k,n,m,S,E;
int g[N][N];
int d[N][N];

void mul(int c[][N],int a[][N],int b[][N]){
    static int temp[N][N];
    memset(temp,0x3f,sizeof temp);
    for(int k = 1;k <= n;++k)
        for(int i = 1;i <= n;++i)
            for(int j = 1;j <= n;++j)
                temp[i][j] = min(temp[i][j],a[i][k] + b[k][j]);
    memcpy(c,temp,sizeof temp);
}

void qpow(){
    memset(d,0x3f,sizeof d);
    for(int i = 1;i <= n;++i)
        d[i][i] = 0;
    while(k){
        if(k & 1)mul(d, d, g);//d = d * g;
        mul(g, g, g);//g = g * g;
        k >>= 1;
    }
}

int main(){
    cin>>k>>m>>S>>E;
    memset(g,0x3f,sizeof g);
    //这里g[i][i]不能置为0，因为这里g[i][j]表示的是从i走1条边到达j,i不能经过1条边到i,因此应该也是INF
    map<int,int>ids;
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&c,&a,&b);
        if(!ids.count(a))ids[a] = ++n;
        if(!ids.count(b))ids[b] = ++n;
        a = ids[a],b = ids[b];

        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    if(!ids[S])ids[S] = ++n;
    if(!ids[E])ids[E] = ++n;
    S = ids[S],E = ids[E];

    qpow();

    cout<<d[S][E]<<endl;
    return 0;

}

View Code

csp赛前刷题篇 图论篇 [USACO07NOV]Cow Relays G

Floyd

csp赛前刷题篇图论篇 [USACO07NOV]Cow Relays G