题目描述
给出一张无向连通图，求S到E经过k条边的最短路。
输入输出样例
输入样例#1：
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
输出样例#1：
10
题解：
法1：dp+floyd+倍增
f[i][j][p]为从i到j经过2^p条边
显然f[i][j][p]=min(f[i][k][p-1]+f[k][j][p-1])
如果n不是2的幂也没事，将n进行二进制分解，再用dp转移
ans[x][i]=min(ans[!x][j]+f[i][j][p]) n的二进制第p位为1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,t,s,e,f[][][],ans[][],num[],pos,logn;
int main()
{int i,d,u,v,p,j,k;
cin>>n>>t>>s>>e;
memset(f,/,sizeof(f));
memset(ans,/,sizeof(ans));
for (i=;i<=t;i++)
{
scanf("%d%d%d",&d,&u,&v);
if (!num[u]) num[u]=++pos;
if (!num[v]) num[v]=++pos;
f[num[u]][num[v]][]=f[num[v]][num[u]][]=d;
}
logn=log2(n);
for (p=;p<=logn;p++)
{
for (k=;k<=pos;k++)
{
for (i=;i<=pos;i++)
{
for (j=;j<=pos;j++)
{
f[i][j][p]=min(f[i][j][p],f[i][k][p-]+f[k][j][p-]);
}
}
}
}
t=;p=;
ans[][num[s]]=;
while (n)
{
if (n&)
{
t=!t;
for (i=;i<=pos;i++)
{ans[t][i]=2e9;
for (j=;j<=pos;j++)
{
ans[t][i]=min(ans[t][i],ans[!t][j]+f[i][j][p]);
}
}
}
p++;
n/=;
}
cout<<ans[t][num[e]];
}
法二：矩阵乘法
可知用邻接矩阵表示时，floyd的过程可以视为矩阵运算，且满足交换律
意思就是先求出走1条边的矩阵，再求出找4条边矩阵
等价于先求出走2条边的矩阵，在求出找3条边矩阵
重载矩阵乘法为floyd的过程，做快速幂就行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,t,s,e,f[][],num[],pos;
struct mat
{
int s[][];
mat()
{int i,j;
for (i=;i<=pos;i++)
for (j=;j<=pos;j++)
s[i][j]=1e9;
}
mat operator*(const mat &x)
{int i,j,k;
mat ans;
for (k=;k<=pos;k++)
{
for (i=;i<=pos;i++)
{
for (j=;j<=pos;j++)
{
ans.s[i][j]=min(ans.s[i][j],s[i][k]+x.s[k][j]);
}
}
}
return ans;
}
}S,T;
int main()
{int i,j,d,u,v;
cin>>n>>t>>s>>e;
for (i=;i<=t;i++)
{
scanf("%d%d%d",&d,&u,&v);
if (!num[u]) num[u]=++pos;
if (!num[v]) num[v]=++pos;
f[num[u]][num[v]]=f[num[v]][num[u]]=d;
}
mat S,T;
for (i=;i<=pos;i++)
for (j=;j<=pos;j++)
if (f[i][j])
S.s[i][j]=T.s[i][j]=f[i][j];
n--;
while (n)
{
if (n&)
{
S=S*T;
}
T=T*T;
n>>=;
}
cout<<S.s[num[s]][num[e]];
}