题解 P6190 【[NOI Online 入门组]魔法（民间数据）】
题解可能有一点长，请耐心看完谢谢
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