跑路:绝佳倍增好题,思路是化 \(2^k\) 为 \(1\) ,倍增起预处理作用。
最近不知道是撞了什么运,前一脚看的是绿题,写完之后交一发,发现直接被 lxl 升蓝了,血赚。
思路:Floyd
首先观察到每次走 \(2^k\) 的代价为 \(1\) ,我们可以预处理出每次走 \(2^i\) 能到哪些点。
但为了让这题的代码更好实现一些,观察到 \(n\) 较小,只有 \(50\) ,于是就可以定义邻接矩阵,\(g[i][j][k]\) 表示从 \(j\) 走 \(2^i\) 步能否到 \(k\) 点,能到即为 \(1\) 。
于是转移方程就出来了,我们枚举一下中点 \(l\) ,然后:
\[g[i][j][k]=g[i][j][k] | (g[i-1][j][l] \& g[i-1][l][k]) \]这样我们就求出某个点能否用 \(1\) 的代价到另一个点,化 \(2^k\) 成 \(1\) 了。
接下来就直接建边,跑 Floyd 或者其他乱七八糟的算法求最短路即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,m,f[55][55];
bitset<55>g[70][55];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
//prepare
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[0][u][v]=1;
}
for(int i=1;i<=64;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
for(int l=1;l<=n;l++)
{
g[i][j][k]=g[i][j][k]|(g[i-1][j][l]&g[i-1][l][k]);
}
}
}
}
//build graph
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)f[i][i]=0;
for(int i=0;i<=64;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(g[i][j][k]==1)f[j][k]=min(f[j][k],1);
}
}
}
//Floyd
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
cout<<f[1][n];
return 0;
}
思路:状压 dp
口胡一下,和上面的那种方法差不多。
首先用 vector 记录下从点 \(i\) 走 \(2^k\) 步能到哪些点,然后就建出了一张图。
接下来从 \(0\) 的状态开始,层层向外拓展能到达的点,最后拓展到 \(n\) 时 break 掉并输出此时拓展的层数即可。
注意状态用 ll 存,int 开不下。
标签:int,题解,状压,55,Floyd,Luogu,倍增,dp From: https://www.cnblogs.com/zhr0102/p/18336917