https://www.luogu.org/problem/P2886
题目描述:
给出一张无向连通图，求\(S\)到\(E\)经过\(k\)条边的最短路。
对于一类\(S\)到\(E\)走指定数量的边数,求它的最短路或条数,都可以采用矩阵快速幂的方式解决.我们回忆一下那一个慢得惊人的\(floyd\)算法,将它的\(dp\)方程式提取出来.
\(floyd[i][j]=min(floyd[i][k]+floyd[k][j])\)
如果我们把\(floyd\)看做一个矩阵,那么矩阵乘法的标准式则为:
\(floyd[i][j]=\sum_{i=1}^{n}(floyd[i][k]×floyd[k][j])\)
我们可以寻找这个方程的本质,可以发现,\((i,j)\)的路径条数可以利用加乘原理,化为\((i,k)×(k,j)\)的和,我们可以考虑这两个\(dp\)方程有什么相似之处.可以发现,上面的那个\(dp\)方程也可以用矩阵乘法的式子替代.我们可以将上面的\(dp\)式定义为矩阵\(min\).现在我们可以考虑k的存在,走\(k\)条边的状态可以由a条边的状态与\(k-a\)条边的状态转移过来,如果我们将走k条边的状态看做一个矩阵,则\(k\)条边的状态可以正好看做\(k\)个\(1\)矩阵相乘,并用矩阵快速“\(min\)"加速.矩阵\(min\)易证是满足结合律的.
原问题便转化为了求一个矩阵的\(k\)次"\(min\)".现在我们来考虑初始状态:当\(k\)=1时,就为邻接矩阵.
注意:矩阵“\(min\)"没有单位元.
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int map[201][201];
};
struct lisan
{
int num,data,newdata;
bool operator < (const lisan &a)const
{
return num<a.num;
}
};
bool cmp(lisan a,lisan b)
{
return a.data<b.data;
}
lisan l[301];
int n,t,s,e,edges[301][3],len,map[1001];
node now,c,res;
node mul(node a,node b)
{
for (int i=1;i<=200;++i)
for (int j=1;j<=200;++j)
c.map[i][j]=1e9;
for (int i=1;i<=200;++i)
for (int j=1;j<=200;++j)
for (int k=1;k<=200;++k)
c.map[i][j]=min(c.map[i][j],a.map[i][k]+b.map[k][j]);
return c;
}
node fast_pow(node a,int b)
{
if (b==1)
return a;
if (b&1)
return mul(fast_pow(mul(a,a),b/2),a);
else
return fast_pow(mul(a,a),b/2);
}
int main()
{
int useless=0;
cin>>n>>t>>s>>e;
for (int i=1;i<=200;++i)
for (int j=1;j<=200;++j)
now.map[i][j]=(1e9);
for (int i=1;i<=t;++i)
{
cin>>edges[i][2]>>edges[i][0]>>edges[i][1];
l[++len].data=edges[i][0];
l[len].num=len;
l[++len].data=edges[i][1];
l[len].num=len;
}
sort(l+1,l+len+1,cmp);
for (int i=1;i<=len;++i)
{
l[i].newdata=i-useless;
map[l[i].data]=l[i].newdata;
if (l[i].data==l[i+1].data)
useless++;
}
sort(l+1,l+len+1);
for (int i=1;i<=t;++i)
now.map[l[i*2-1].newdata][l[i*2].newdata]=now.map[l[i*2].newdata][l[i*2-1].newdata]=min(now.map[l[i*2-1].newdata][l[i*2].newdata],edges[i][2]);
res=fast_pow(now,n);
cout<<res.map[map[s]][map[e]]<<endl;
return 0;
}