ACWing 345 牛站 题解

ACWing 345 牛站 题解

题意

给定一张有$t$条边的无向图($1\leq t\leq 100$,点的标号在$[1,1000]$之间),求从$s$到$t$恰好经过$n$条边的最短路()$1\leq n\leq 10^6$).注：答案保证有解.

题解

众所周知,$floyd$的邻接矩阵是用来矩阵乘的好东西,又注意到虽然点是$[1,1000]$很大不好计算,但是边只有$100$条,所以考虑先进行离散化.如果我们把原图的邻接矩阵表示视为一个矩阵$A^0$,记$A^x$为经过恰好$x$步的最短路,那么所以不难发现满足如下的性质:

$定于广义的矩阵乘法为A=B\times C满足A_{i,j}=max_{k=1}^{2t}\{b_{i,k}+c_{k,j}\}\\则发现A^{p+q}=A^p\times A^q且矩阵满足分配律$

所以我们可以愉快地使用矩阵快速幂进行求解,时间复杂度$O(8t^3\log n)$.

于是，笔者愉快的写了递归的快速幂,并且成功地使自己的电脑在递归时爆了栈.

在此时间压的比较紧,虽说复杂度是$O(8t^3\log n)$,但实际上这个复杂度是跑不满的,只有在原图是一棵树时能够跑满.,显然出题人并没有刻意卡这种图,所以建议使用非递归快速幂+小小的卡常就可以过.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=210;
const int inf=999999999;
int n,t,s,e;
int cnt;
struct Matrix{
    int a[MAXN][MAXN];
    friend Matrix operator *(const Matrix &x,const Matrix &y)//重载乘法运算
    {
        register Matrix ret;
        for(register int i=1;i<=cnt;i++)
        for(register int j=1;j<=cnt;j++) ret.a[i][j]=inf;
        for(register int i=1;i<=cnt;i++)
        for(register int j=1;j<=cnt;j++)
        for(register int k=1;k<=cnt;k++)
        ret.a[i][j]=min(ret.a[i][j],x.a[i][k]+y.a[k][j]);
        return ret;
    }
}f;
int b[210];
map<int,int> mp;
struct node{
    int u,v,c;
}a[110];
inline void prework()//离散化
{
    cnt=0;
    sort(b+1,b+2*t+1);
    for(int i=1;i<=2*t;i++)
    if(!mp[b[i]]) mp[b[i]]=++cnt;
    for(int i=1;i<=t;i++) a[i].u=mp[a[i].u],a[i].v=mp[a[i].v];
    s=mp[s],e=mp[e];//千万别忘了对起点和终点进行同样的离散化
}
int main()
{
    read(n),read(t),read(s),read(e);
    for(int i=1;i<=200;i++)
    for(int j=1;j<=200;j++) f.a[i][j]=inf;
    for(int i=1;i<=t;i++) read(a[i].c),read(a[i].u),read(a[i].v),b[2*i-1]=a[i].u,b[2*i]=a[i].v;
    prework();
    for(int i=1;i<=t;i++) f.a[a[i].u][a[i].v]=f.a[a[i].v][a[i].u]=min(f.a[a[i].u][a[i].v],a[i].c);
	register Matrix cur=f,ans;
	bool book=1;
    while(n)//非递归快速幂
	{
		if(n&1)
		{
			if(book) book=0,ans=cur;
			else ans=ans*cur;
		}
		n>>=1;
		cur=cur*cur;
	}
    write(ans.a[s][e]),putchar('\n');
	return 0;
}