题目传送门

大致题意:

给定一张$n$个结点$m$条边的有向图,边权固定为1,每秒可以移动$2^t$($t$为任意值)。求从$1$到$n$的最短所需时间。

其中$n\leq 50,m\leq 10000,dis_{1-n}\leq int_{max}$。


第一眼是个最短路,然后发现不对劲。

因为从$1$到$n$的最短路不一定是所求答案,即二进制下$1$的个数不一定最少。

举个栗子:

在这张图中,很明显最短路是$1-2-4-7$,但需要$2+1$共$2$秒。而另一条路虽然长度为$4$,但只需要一次$2^2$就可以到达,时间只需要$1$秒。

于是我们需要根据题目中$2^t$这个提示,考虑如何融入倍增的思想。

最终的算法肯定还是落脚在最短路上,但是这个边不应该是最初输入进来的,而是通过我们的计算,可以一步到达的两个点之间连边。

什么情况下两个点可以一步到达?

对于$(u,v)$是否能通过一个$2^t$跨过去,我们如果能找到一个$k$满足$(u,k)$能够$2^{t-1}$跨过去,并且,$(k,v)$

也可以$2^{t-1}$跨过去,那就一定可行。

于是考虑用$dp[u][v][t]$表示,从$u$到$v$是否能移动$2^t$到达。

对于输入的边$(u,v)$,当然是可以通过$2^0$距离到达的,那么$dp[u][v][0]=1$。并连上$u$和$v$。

此外就如上所述,遍历其他点$k$,如果有dp[u][k][t-1]&dp[k][v][t-1]==1,那么dp[u][v][t]=1,并且把$u$,$v$连上。

完成了建边之后,直接跑最短路即可。考虑到$n$的范围只有$50$,于是方便地选用$Floyd$。

另外,$t$只需要枚举到$31$即可($int_{max}=2^{31}-1$)。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=70;
int dis[N][N],dp[N][N][N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        dis[u][v]=1;
        dp[u][v][0]=1;
    }
    for(int t=1;t<32;t++)
        for(int k=1;k<=n;k++)
            for(int u=1;u<=n;u++)
                for(int v=1;v<=n;v++)
                    if(dp[u][k][t-1]&dp[k][v][t-1])
                        dis[u][v]=dp[u][v][t]=1;
    for(int k=1;k<=n;k++)
        for(int u=1;u<=n;u++)
            for(int v=1;v<=n;v++)
                dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);
    printf("%d\n",dis[1][n]);
    return 0;
}
最后修改:2020 年 08 月 17 日 09 : 57 PM