首页 - 新闻 - 【解法】luogu_P1613逃逸（最短路径/加倍）

【解法】luogu_P1613逃逸（最短路径/加倍）

2023-10-08 03:27

-->

首先你要知道你不能跑最短路径，因为一秒只能到达2^k，这与倍增有关

所以我們想知道任意兩點間是否可以拥有长度为 2^k 的路径。數據个子小，可以考虑弗洛伊德

结合doubling和floyd发现，如果i到k和k到j各有2^(k-1长的路径，那么i和j之間就有2^k长的路径

所以更新实际时间后，對時間就可以运行弗洛伊德一次了

#包括
使用命名空间 std;
int n,m;
长长d[][];
bool f[][][];//i,j是否存在长度为2^k的路径
int main()
{
scanf("%d%d",&n,&m);
memset(d,,sizeof(d));
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
d[x][y]=;f[x][y][]=;
}
//和floyd类似，i,j到t的长度都是2^(k-1)，那么i,j之間就有2^k长度的路径
for(int k=;k<=;k++)
for(int t=;t<=n;t++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(f[i][t][k-] && f[t][j][k-])
f[i][j][k]=,d[i][j]=;
//真正的弗洛伊德
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
printf("%lld",d[][n]);
} -->

相关推荐