自动搬运

查看原文

来自洛谷，原作者为

	R_8x 你充Q币吗

搬运于2025-08-24 23:14:34，当前版本为作者最后更新于2025-05-23 18:41:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12319 [蓝桥杯 2024 国研究生组] 最短路 - 题解

前置知识：分层图最短路，矩阵加速。

在尝试此题前建议先完成 P2886 [USACO07NOV] Cow Relays G。

正文

首先，题中提到了一项机制：对于每次询问，可以把一条边的边权整除 $2$，但每次询问只有可以进行一次此操作（即使多次经过一条边也只生效一次），所以考虑拆点：每个点有两种状态：进行过整除操作和没进行过，对拆开的两个点分别连边。

假设题中从 $u$ 向 $v$ 连了一条有向边，边权为 $w$，则对于拆出的点 $u'$ 和点 $v'$，我们需要额外从 $u$ 向 $v'$ 连一条边权为 $\frac{w}{2}$ 的边，代表在此处进行整除操作，当然，也要从 $u'$ 向 $v'$ 连一条边权为 $w$ 的边，代表进行过整除操作操作的情况。

由于题中的 $c_i \le 10^9$，所以使用矩阵乘法进行加速，其余部分就和 P2886 一样了……吗？

由于这道题需要进行 $m$ 次操作，而 $m \le 1000, n \le 50$，同时我们还进行了拆点，所以矩阵大小为 $100 \times 100$，则总的时间复杂度为 $O((2 \times n)^3 \times m\log{c_i})$，不能通过此题。

注意到，我们可以使用倍增进行预处理，处理出经过 $2^0$ 条边到 $2^{30}$ 条边的矩阵，然后对每次询问的 $c_i$ 进行拆位计算，减少矩阵乘法的次数。但这种优化实际上只减少了常数时间复杂度，并没有改变根本。然而，由于每次询问都给出了起点 $s$，我们可以把初始矩阵中的第 $s$ 行单独提取出来，然后再与倍增预处理出的矩阵进行矩阵乘法，这样单次计算的时间复杂度由 $O((2 \times n)^3)$ 变成了 $O((2 \times n)^2)$，同时保证了以 $s$ 为起点的值正确，此题解决。

时间复杂度：预处理部分为 $O(30 \times (2\times n)^3)$，查询部分为 $O(m \times (2 \times n)^2 \times \log{c_i})$。

以下为代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//记得开 long long 
const ll inf=0x3f3f3f3f3f3f3f3f;
struct node
{
	int n,m;
	ll mp[105][105];
	node(){memset(mp,0x3f,sizeof(mp));}//在使用了 node(int x,int y) 这一构造函数后，直接开node数组无法通过编译，所以要加这一行 
	node(int x,int y){n=x,m=y,memset(mp,0x3f,sizeof(mp));}
	node operator * (node x)
	{
		int z=x.m;
		node res(n,z);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=z;j++)
				for(int k=1;k<=m;k++)
					res.mp[i][j]=min(res.mp[i][j],mp[i][k]+x.mp[k][j]);//广义矩阵乘法 
		return res;
	}
};
node to[35];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,q;
	cin>>n;
	node a(n*2,n*2);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int x;
			cin>>x;
			if(x!=0)
			{
				a.mp[i][j]=x;
				a.mp[i][j+n]=x/2;
				a.mp[i+n][j+n]=x;//拆点 
			}
		}
	}
	to[0]=a;
	for(int i=1;i<=30;i++)
		to[i]=to[i-1]*to[i-1];//倍增 
	cin>>q;
	while(q--)
	{
		int s,t,k;
		cin>>s>>t>>k;
		node st(1,n*2);
		for(int i=1;i<=n*2;i++)
			st.mp[1][i]=a.mp[s][i];
		k--;//k要减一，因为 k==1 为初始矩阵的情况，而进行一次乘法后为经过 2 条边的情况 
		for(int i=0;i<=30;i++)
			if(k&(1<<i))
				st=st*to[i];
		ll ans=min(st.mp[1][t],st.mp[1][t+n]);
		cout<<(ans==inf?-1:ans)<<"\n";
	}
	return 0;
}