莫欺少年穷,修魔之旅在这开始—>算法提高课题解
思路:
1. 首先要离散化,因为区间大但点数少
2. 其次是需要通过倍增的思想来计算,因为需要经过的边数很大
3. d[a + b, i, j] = min(d[a + b, i, j], d[a, i, k] + d[b, k, j])
4. 从 i 到 j 经过 a+b 条边的 min = 从 i 到 k 经过 a 条边的 min + 从 k 到 j 经过 b 条边的 min
5. 故枚举所有的 k 点即可,类似于 Floyd 算法
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int k,n,m,S,E;
int g[N][N],res[N][N];
map<int,int> ids;
void mul(int c[][N],int a[][N],int b[][N])
{
int temp[N][N];
memset(temp,0x3f,sizeof temp);
//从 i 到 j 经过 k 这个点的最短距离
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]);
memcpy(c,temp,sizeof temp);
}
void qmi()
{
memset(res,0x3f,sizeof res);
for(int i=1;i<=n;i++) res[i][i]=0;
//倍增的思想,只经过 k 条边
while(k)
{
if(k&1) mul(res,res,g);
mul(g,g,g);
k>>=1;
}
}
int main()
{
cin>>k>>m>>S>>E;
memset(g,0x3f,sizeof g);
while(m--)
{
int c,a,b;
cin>>c>>a>>b;
//离散化
if(!ids.count(a)) ids[a]=++n;
if(!ids.count(b)) ids[b]=++n;
a=ids[a],b=ids[b];
g[a][b]=g[b][a]=c;
}
qmi();
cout<<res[ids[S]][ids[E]]<<endl;
return 0;
}