15011418730 LV 7 @ 2025-8-24 22:18:23

自动搬运

来自洛谷，原作者为

	gaozitao1 1307314354

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

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

以下是正文

题解可能有一点长，请耐心看完谢谢

~~2020年CCF入门组测试出两个紫题，提高组都只是3个蓝题。。。~~

题目大意：有一个n个点，m条边的图，你可以使用k此魔法，使通过下一条道路时，距离变为原来的相反数，问从1到n的最小距离。

~~前置知识：dfs,Floyd,spfa(默认为大家都会qwq~~

30分

显然当k=0时，就是一个最短路的板子题，因为n的范围太小了，所以用Floyd就可以了。Floyd应该都会吧。。。 30分代码：

#include<cmath>
#include<cstdio>
#include<iostream>
const short M(2501),N(101);//比规定值大1即可
const long long I(2500000000001);//无穷大为m*t（边权）+1
long long d[N][N];//d[i][j]表示从i到j的最小距离
int main()
{
	short i,j,l,m,n,u,v;
	int k,t;
	scanf("%hd%hd%d",&n,&m,&k);//输入，虽然不需要k,但是还是要输入
	for(i=1; i<=n; ++i)
		for(j=1; j<=n; ++j)
			if(i!=j)//如果i==j，d[i][j]=0
				d[i][j]=I;//否则，赋值成无穷大
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u,&v,&t);//输入边
		d[u][v]=t;//存边
	}
	for(l=1; l<=n; ++l)//Floyd板子（加上了一点优化）
		for(i=1; i<=n; ++i)
			if(i!=l)//如果i=l，下面的式子就变成了d[i][j]=min(d[i][j],d[i][i]+d[i][j]),而d[i][i]=0，不用做了
				for(j=1; j<=n; ++j)
					if(i!=j&&j!=l&&d[i][j]>d[i][l]+d[l][j])//同上
						d[i][j]=d[i][l]+d[l][j];
	printf("%lld",d[1][n]);//输出从1到n的最小值
	return 0;
}

50分Floyd

可以发现，当这一张图是一张有向无环图时，每一条边最多走一遍，所以一开始处理的时候可以全部记录成负数，就可以把这一部分AC了。

50分Floyd代码：

#include<cmath>
#include<cstdio>
#include<iostream>
const short M(2501),N(101);//比规定值大1即可
const long long I(2500000000001);//无穷大为m*t（边权）+1
long long d[N][N];//d[i][j]表示从i到j的最小距离
int main()
{
	short i,j,l,m,n,u,v;
	int k,t;
	scanf("%hd%hd%d",&n,&m,&k);//输入
	for(i=1; i<=n; ++i)
		for(j=1; j<=n; ++j)
			if(i!=j)//如果i==j，d[i][j]=0
				d[i][j]=I;//否则，赋值成无穷大
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u,&v,&t);//输入
		if(k)//能使用魔法
			d[u][v]=-t;//使用魔法
		else//不能使用魔法
			d[u][v]=t;//不使用魔法
	}
	for(l=1; l<=n; ++l)//Floyd板子（加上了一点优化）
		for(i=1; i<=n; ++i)
			if(i!=l)//如果i=l，下面的式子就变成了d[i][j]=min(d[i][j],d[i][i]+d[i][j]),而d[i][i]=0，不用做了
				for(j=1; j<=n; ++j)
					if(i!=j&&j!=l&&d[i][j]>d[i][l]+d[l][j])//同上
						d[i][j]=d[i][l]+d[l][j];
	printf("%lld",d[1][n]);//输出从1到n的最小值
	return 0;
}

50分搜索

这一道题用搜索也可以得50分。

50分dfs代码：

#include<cmath>
#include<cstdio>
#include<iostream>
const short M(2501),N(101);//比规定值大1即可
const long long I(2500000000001);//无穷大为m*t（边权）+1
short c,e[M],h[N],n,o[M];
int w[M];
long long a(I);//先赋值成无穷大
inline void add(short u,short v,int x)
{
	e[++c]=h[u];
	h[u]=c;
	o[c]=v;
	w[c]=x;
}//spfa建边
inline void dfs(short b,int d,long long f)//b表示当前点，d表示剩余魔法次数，f表示价值
{
	if(a<=f&&d==0)//如果价值大于最小值
		return;//直接返回
	if(b==n)//如果到终点
		if(a>f)//记录最小值
			a=f;//因为n号点可以经过好几次，所以不要return
	short i;
	for(i=h[b]; i; i=e[i]) //spfa遍历边
	{
		dfs(o[i],d,f+w[i]);//不使用魔法
		if(d>0)//可以使用魔法
			dfs(o[i],d-1,f-w[i]);
	}
}
int main()
{
	short i,m,u,v;
	int k,t;
	scanf("%hd%hd%d",&n,&m,&k);
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u,&v,&t);//输入
		add(u,v,t);//建边
	}
	dfs(1,k,0);
	printf("%lld",a);//输出结果
	return 0;
}

70分

这一道题也是一个dp题，可以先处理使用0次和1次魔法的情况，之后用动态规划求出使用2到k次魔法的情况。

首先是几个状态转移方程：

1 不使用魔法

d[i][j][0]=min（d[i][j][0]，d[i][l][0]+d[l][j][0]）

Floyd的状态转移方程，相信大家都会

2 使用一次魔法

d[i][j][1]=min（d[i][j][0]，d[i][j][1]）

使用魔法之后距离肯定不超过不使用魔法的距离

d[i][j][1]=min（d[i][j][1]，d[i][u[l]][0]+d[v[k]][j][0]-t[l]）

d[i][u[l]][0]表示从i到第l条边的起点的距离

d[v[k]]][j][0]表示从第l条边的终点到j的距离

d[i][u[l]][0]+d[v[k]][j][0]-t[l]表示从i到j走第l条边并在第l条边使用魔法的距离

所以原式表示不使用魔法和在第l条边使用魔法的最小距离

3 使用k次魔法

d[i][j][p]=min（d[i][j][p]，d[i][l][p-1]+d[l][j][1]）

从i到j使用p次魔法的最小距离是本身或从i到l使用p-1次魔法和从l到j使用1次魔法的最小值

为什么一个是p-1一个是1呢？

因为1已经提前求出来了，所以其中一个一定是1，而p-1在上一步也已经求出来了，所以一个是1一个是p-1，才能保证总数为p。把1和p-1的位置换过来也是可以的，因为经过循环两种情况都会做一遍

70分代码：

#include<cmath>
#include<cstdio>
#include<iostream>
const short K(1001),M(2501),N(101);//比规定范围大1即可
const long long I(2500000000001);//规定无穷大为n*t（边权）+1即可
long long d[N][N][K];//注意开long long，K太大会MLE
//d[i][j][l]表示从i到j最多使用l吃次魔法时的最小距离
int main()
{
	short i,j,l,m,n,p,u[M],v[M];
	int k,o,t[M];
	scanf("%hd%hd%d",&n,&m,&k);//输入
	for(o=0; o<=k; ++o)
		for(i=1; i<=n; ++i)
			for(j=1; j<=n; ++j)
				d[i][j][o]=I;//初始化成最大值
	for(i=1; i<=n; ++i)
		d[i][i][0]=0;//自己到自己为0
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u[i],&v[i],&t[i]);//输入
		d[u[i]][v[i]][0]=t[i];
	}
	//先处理不使用魔法的情况
	for(l=1; l<=n; ++l)//Floyd板子（加上了一些小小的优化）
		for(i=1; i<=n; ++i)
			if(i!=l)//如果i=l，下面的式子就变成了d[i][j][0]=min(d[i][j][0],d[i][i][0]+a[i][j][0]),而d[i][i][0]=0，可以不用做
				for(j=1; j<=n; ++j)
					if(i!=j&&j!=l&&d[i][j][0]>d[i][l][0]+d[l][j][0])//道理同上
						d[i][j][0]=d[i][l][0]+d[l][j][0];
	//再处理使用1次魔法的情况
	for(l=1; l<=m; ++l) //枚举使用魔法的边
		for(i=1; i<=n; ++i)
			for(j=1; j<=n; ++j) //枚举两个点
			{
				if(d[i][j][0]<d[i][j][1])
					d[i][j][1]=d[i][j][0];//先记录上一次的结果
				if(d[i][j][1]>d[i][u[l]][0]+d[v[l]][j][0]-t[l])
					d[i][j][1]=d[i][u[l]][0]+d[v[l]][j][0]-t[l];//判断经过第l条使用魔法的边后距离是否变短
			}
	for(p=2; p<=k; ++p) //枚举使用几次魔法，从2开始就可以了
		for(l=1; l<=n; ++l) //枚举转折点
			for(i=1; i<=n; ++i) //枚举起点
				for(j=1; j<=n; ++j) //枚举终点
					if(d[i][j][p]>d[i][l][p-1]+d[l][j][1])
						d[i][j][p]=d[i][l][p-1]+d[l][j][1];
	//从i到j使用p次魔法的最小距离是本身或从i到l使用p-1次魔法和从l到j使用1次魔法的最小值
	printf("%lld",d[1][n][k]);//输出从1到n最多使用k次魔法的最小距离
	return 0;
}

90分

分层图做法，每一次使用魔法就往下走一层。

核心建边：

第一个循环枚举每一条边，第二个循环枚举每一层，循环中第一行表示建立每一层横着的边，第二行表示从上一层到这一层的边。

之后，再跑一边spfa就可以了。

注意！！！spfa要修改！！！

90分代码：

#include<cmath>
#include<cstdio>
#include<iostream>
#include<queue>
using std::queue;
const short K(1001),M(2501),N(101);//比最大值大1即可
const long long I(2500000000001);//无穷大时m*t（边权）+1
//有n*k+n个点，2*m*k+m条边
int c,e[M+2*K*M],h[N+N*K],k,m,n,o[M+2*K*M],w[M+2*K*M];
long long d[N+N*K];
inline void add(int u,int v,int x)
{
	e[++c]=h[u];
	h[u]=c;
	o[c]=v;
	w[c]=x;
}//spfa建边
//spfa模板\注意，这一个spfa不需要bool数组，加上只能得到75分\这一个卡spfa的方式好奇怪
inline void spfa(short s)
{
	int i,u;
	queue<int>q;
	for(i=1; i<=n+n*k; ++i)
		d[i]=I;
	d[s]=0;
	q=queue<int>();
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(i=h[u]; i; i=e[i])
			if(d[o[i]]>d[u]+w[i])
			{
				d[o[i]]=d[u]+w[i];
				q.push(o[i]);
			}
	}
}
int main()
{
	int i,j,u[M],v[M],t[M];
	long long a(I);//要求最小值，先赋值成最大值
	scanf("%d%d%d",&n,&m,&k);//输入
	for(i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&u[i],&v[i],&t[i]);//输入
		add(u[i],v[i],t[i]);//spfa建边
	}
	for(i=1; i<=m; ++i)//建立分层图
		for(j=1; j<=k; ++j)
		{
			add(u[i]+n*j,v[i]+n*j,t[i]);//建立横着的边
			add(u[i]+n*(j-1),v[i]+n*j,-t[i]);//建立斜着的边
		}
	spfa(1);//spfa
	for(i=n; i<=n+n*k; i+=n)
		if(a>d[i])
			a=d[i];//寻找最小值，注意最小值不一定是n*k+n，必须遍历每一层的n
	printf("%lld",a);
	return 0;
}

100分

会发现，70分的dp做法无论是时间还是空间，都过不了这一道题的限制（1s，250MB）

所以要进行优化（100分做法）。

优化之前，先大概讲一下本题用到的知识：矩阵快速幂。

矩阵快速幂实质上就是快速幂和矩阵乘法的合体

快速幂：

众所周知，求a的b次方普通做法的时间复杂度为O（b），而快速幂的时间复杂度为O（logb）

求a的b次方普通做法可以用循环解决。考虑优化一下，如果提前算出a的平方，那么a的b次方，时间复杂度为O（b/2），如果继续算出了a的4次方、8次方、16次方等，那么就相当于对b进行了二进制拆分，时间复杂度就变成了O（logb）

~~P1226的题解中有详细的讲解~~

代码：

inline int quickpower(int x,int y)
{
    int a(1),c(x);
    while(y)//y!=0
    {
        if(y&1)//y%2==1
            a*=c;//a=a*c
        c*=c;//c=c*c
        y>>=1;//y=y/2
    }
    return a;
}

矩阵乘法：

一个nm的矩阵可以和一个mo的矩阵相乘得到一个n*o的矩阵，n，m，o可以相同，m和m必须一样，两个矩阵相乘必须第一个矩阵的列和第二个矩阵的行相同。

结果矩阵的第i行第j列结果是a矩阵的第i行的每一个数乘上b矩阵的第j列的每一个数。

代码：

struct jz
{
	int e[N][N],m,n;//n记录行，m记录列
} a,b;
jz operator*(const jz &x,const jz &y)//重载运算符
{
	short i,j,k;
	jz z;
	z.n=x.n;//记录边长
	z.m=y.m
	for(i=1; i<=z.n; ++i)
		for(j=1; j<=z.m; ++j)
			z.e[i][j]=0;//清零
	for(k=1; k<=x.m; ++k)
		for(i=1; i<=x.n; ++i)
			for(j=1; j<=y.m; ++j)
				z.e[i][j]+=x.e[i][k]*y.e[k][j];//矩阵乘法核心代码
	return z;
}

矩阵快速幂：

由矩阵乘法的定义可知，如果a*a合法，那么a的行等于a的列，所以可以快速幂的矩阵必须是方阵（行和列相等）

之后，快速幂中有一个a，初始化为1，那么矩阵快速幂中的1是什么呢？之所以定义为1，因为任何数乘1都等于它本身，所以，一定要找到一个方阵a，使与a边长相同的矩阵乘a结果等于它本身。

这里的a是单位矩阵，只有对角线是1，其他的值都为0，这时能保证与a边长相同的矩阵乘a结果等于它本身。

之后，矩阵快速幂和快速幂基本上就差不多了。

代码：

#include<cmath>
#include<cstdio>
#include<iostream>
const short N(101);
struct jz
{
	int e[N][N],n;//n记录边长
} a,b;
jz operator*(const jz &x,const jz &y)//重载运算符
{
	short i,j,k;
	jz z;
	z.n=x.n;//记录边长
	for(i=1; i<=z.n; ++i)
		for(j=1; j<=z.n; ++j)
			z.e[i][j]=0;//清零
	for(k=1; k<=z.n; ++k)
		for(i=1; i<=z.n; ++i)
			for(j=1; j<=z.n; ++j)
				z.e[i][j]+=x.e[i][k]*y.e[k][j];//矩阵乘法核心代码
	return z;
}
inline jz qp(jz x,int y)//求x的y次方
{
	short i,j;
	jz c,d(x);
	c.n=x.n;
	for(i=1; i<=c.n; ++i)
		for(j=1; j<=c.n; ++j)
			if(i!=j)
				c.e[i][j]=0;
			else
				c.e[i][j]=1;//定义单位矩阵
	while(y)
	{
		if(y&1)
			c=c*d;//注意，不能写成c*=d，因为重载的是*，不是*=
		d=d*d;
		y>>=1;
	}//快速幂模板
	return c;
}
int main()
{
	short c,i,j,n;
	scanf("%hd%hd",&n,&c);
	a.n=n;//记录边长
	for(i=1; i<=n; ++i)
		for(j=1; j<=n; ++j)
			scanf("%d",&a.e[i][j]);//输入
	b=qp(a,c);//求a的c次方
	for(i=1; i<=n; ++i)
	{
		for(j=1; j<=n; ++j)
			printf("%d ",b.e[i][j]);
		putchar('\n');//输出
	}
	return 0;
}

好了，再次回归本题的100分做法。

前面与70分做法差不多。

代码（部分）：

#include<cmath>
#include<cstdio>
#include<iostream>
const short M(2501),N(101);//比规定范围大1即可
const long long I(2500000000001);//规定无穷大为n*t（边权）+1即可
long long d[N][N];//存不使用魔法时的距离，注意开long long
int main()
{
	short i,j,l,m,n,u[M],v[M];
	int k,t[M];
	scanf("%hd%hd%d",&n,&m,&k);
	for(i=1; i<=n; ++i)
		for(j=1; j<=n; ++j)
			if(i!=j)
				d[i][j]=I;//初始化成最大值
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u[i],&v[i],&t[i]);//输入
		d[u[i]][v[i]]=t[i];
	}
	//先处理不使用魔法的情况
	for(l=1; l<=n; ++l)//Floyd板子（加上了一些小小的优化）
		for(i=1; i<=n; ++i)
			if(i!=l)//如果i=l，下面的式子就变成了d[i][j]=min(d[i][j],d[i][i]+a[i][j]）,而d[i][i]=0,不用做
				for(j=1; j<=n; ++j)
					if(i!=j&&j!=l&&d[i][j]>d[i][l]+d[l][j])//道理同上
						d[i][j]=d[i][l]+d[l][j];
	if(k)//可以使用魔法
	{
		//再处理使用1次魔法的情况
		a.n=n;
		for(i=1; i<=n; ++i)
			for(j=1; j<=n; ++j)
				a.e[i][j]=d[i][j];//先存储不使用魔法的情况
		for(l=1; l<=m; ++l) //枚举使用魔法的边
			for(i=1; i<=n; ++i)
				for(j=1; j<=n; ++j) //枚举两个点
					if(a.e[i][j]>d[i][u[l]]+d[v[l]][j]-t[l])
						a.e[i][j]=d[i][u[l]]+d[v[l]][j]-t[l];//判断经过第l条使用魔法的边后距离是否变短
		//输出结果
		return 0;//结束
	}
	printf("%lld",d[1][n]);//不能使用魔法
	return 0;
}

通过70分做法中的状态转移方程：

d[i][j][q]=min(d[i][j][q]，d[i][k][q-1]+d[k][j][1])

其实还可以写成：

d[i][j][x+y]=min(d[i][j][x+y]，d[i][k][x]+d[k][j][y])

会发现，如果把+换成*，把min换成“求和”，那么就和矩阵乘法长得差不多了，所以可以把矩阵乘法的代码稍微改一下，求最小值：

之后，就只剩下最后一个求值部分了。

注意，接下来的矩阵乘法是修改过的矩阵乘法，不是原本的矩阵乘法

用70分做法，把样例1的dp数组打表后结果如下（I表示无穷大）：

不使用魔法：

0 5 9 10

I 0 4 5

I I 0 1

I I I 0

使用1次魔法：

I -5 -1 0

I 0 -4 -3

I I 0 -1

I I I 0

使用两次魔法：

0 -5 -9 -8

I 0 -4 -5

I I 0 -1

I I I 0

会发现，用修改过的矩阵乘法，第一个矩阵乘上第二个矩阵就是第二个矩阵，第一个矩阵乘上第二个矩阵的平方就是第三个矩阵，如果继续打表出使用三次魔法的矩阵，会发现，第一个矩阵乘上第二个矩阵的三次方就是第四个矩阵。

总结：用第一个矩阵（不使用魔法的矩阵）乘上第二个矩阵（使用1次魔法的矩阵）的k次方相当于使用k次魔法。

所以结果就是不使用魔法的矩阵乘上使用一次魔法的矩阵的k次方。

又可以发现，原来的快速幂是单位矩阵乘上矩阵的k次方，所以可以吧单位矩阵换成不使用魔法的矩阵即可

“矩阵快速幂”代码：

如果不使用矩阵快速幂，时间复杂度和70分做法相同（又一次证明了算法的正确性），但是使用矩阵快速幂，时间复杂度就可以降到O（n2m+n3logk），而logk最大为20，所以可以忽略，时间复杂度为O（n2m），空间复杂度为O（n2）。

完整满分代码：

#include<cmath>
#include<cstdio>
#include<iostream>
const short M(2501),N(101);//比规定范围大1即可
const long long I(2500000000001);//规定无穷大为n*t（边权）+1即可
long long d[N][N];//存不使用魔法时的距离，注意开long long
struct jz
{
	short n;
	long long e[N][N];
} a;
jz operator*(const jz &x,const jz &y)//重载运算符
{
	short i,j,k;
	jz z;
	z.n=x.n;//记录结果矩阵的边长
	for(i=1; i<=z.n; ++i)
		for(j=1; j<=z.n; ++j)
			z.e[i][j]=I;//因为要求最小值，先赋值成最大值
	for(k=1; k<=z.n; ++k)
		for(i=1; i<=z.n; ++i)
			for(j=1; j<=z.n; ++j)
				if(x.e[i][k]+y.e[k][j]<z.e[i][j])
					z.e[i][j]=x.e[i][k]+y.e[k][j];//改成min
	return z;//返回
}
inline jz qp(jz x,int y)//求x的y次方
{
	short i,j;
	jz e,f(x);//f=x
	e.n=x.n;//记录边长
	for(i=1; i<=e.n; ++i)
		for(j=1; j<=e.n; ++j)
			e.e[i][j]=d[i][j];//先赋值成d矩阵
	while(y)
	{
		if(y&1)
			e=e*f;//注意，不可以写成d*=e，因为重载的运算符是*，不是*=
		f=f*f;//同上
		y>>=1;
	}//快速幂模板
	return e;
}
int main()
{
	short i,j,l,m,n,u[M],v[M];
	int k,t[M];
	scanf("%hd%hd%d",&n,&m,&k);
	for(i=1; i<=n; ++i)
		for(j=1; j<=n; ++j)
			if(i!=j)
				d[i][j]=I;//初始化成最大值
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u[i],&v[i],&t[i]);//输入
		d[u[i]][v[i]]=t[i];
	}
	//先处理不使用魔法的情况
	for(l=1; l<=n; ++l)//Floyd板子（加上了一些小小的优化）
		for(i=1; i<=n; ++i)
			if(i!=l)//如果i=l，下面的式子就变成了d[i][j]=min(d[i][j],d[i][i]+a[i][j]）,而d[i][i]=0,不用做
				for(j=1; j<=n; ++j)
					if(i!=j&&j!=l&&d[i][j]>d[i][l]+d[l][j])//道理同上
						d[i][j]=d[i][l]+d[l][j];
	if(k)//可以使用魔法
	{
		//再处理使用1次魔法的情况
		a.n=n;
		for(i=1; i<=n; ++i)
			for(j=1; j<=n; ++j)
				a.e[i][j]=d[i][j];//先存储不使用魔法的情况
		for(l=1; l<=m; ++l) //枚举使用魔法的边
			for(i=1; i<=n; ++i)
				for(j=1; j<=n; ++j) //枚举两个点
					if(a.e[i][j]>d[i][u[l]]+d[v[l]][j]-t[l])
						a.e[i][j]=d[i][u[l]]+d[v[l]][j]-t[l];//判断经过第l条使用魔法的边后距离是否变短
		printf("%lld",qp(a,k).e[1][n]);//输出结果
		return 0;//结束
	}
	printf("%lld",d[1][n]);//不能使用魔法
	return 0;
}

orz

ID

4222

时间

1000ms

内存

250MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

30分

50分Floyd

50分搜索

70分

90分

100分

快速幂：

矩阵乘法：

矩阵快速幂：

[NOI Online #1 入门组] 魔法

信息

1 条题解

自动搬运

以下是正文

30分

50分Floyd

50分搜索

70分

90分

100分

快速幂：

矩阵乘法：

矩阵快速幂：

[NOI Online #1 入门组] 魔法

信息

还没有账户？

登录