Problem

小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 6：00 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个十分牛 B 的空间跑路器，每秒钟可以跑 2^k 千米（k 是任意自然数）。当然，这个机器是用 longint 存的，所以总跑路长度不能超过 maxlongint 千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 1，公司为点 n，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 1 到 n 至少有一条路径。

Solution

本题操作有点骚。
对其进行可行性 dp 之后，我们再以得到的 dp 数组进行松弛。

令 dpi[k] 代表点 i 跑 2^k 条边能到达的点。
然后得到这个数组跑个最短路就行。

数组的转移不难想，但不太好用式子表示。
加上 Dijkstra，总体复杂度约是 $O(64n^3)$，即约 $O(n^4)$。

这个还有点难想到。我想的还比较久... 但代码不难打 233

Code

// Code by ajcxsu
// Problem: Running
#include<bits/stdc++.h>
using namespace std;

const int N=51,OP=64,M=1e4+10;
int n,m;
bool dp[N][OP][N];

int dijkstra(int s,int t) {
    int dist[N];
    bool S[N];
    memset(dist,0x3f,sizeof(dist)), memset(S,0,sizeof(S));
    dist[s]=0;
    for(int i=1;i<=n;i++) {
        int u=0;
        for(int j=1;j<=n;j++)
            if(!S[j] && dist[j]<dist[u]) u=j;
        S[u]=1;
        for(int j=0;j<OP;j++)
            for(int k=1;k<=n;k++)
                if(dp[u][j][k] && !S[k] && dist[k]>dist[u]+1)
                    dist[k]=dist[u]+1;
    }
    return dist[t];
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++) cin>>u>>v, dp[u][0][v]=1;
    for(int j=1;j<OP;j++)
        for(int i=1;i<=n;i++)
            for(int k=1;k<=n;k++)
                if(dp[i][j-1][k])
                    for(int kk=1;kk<=n;kk++)
                        dp[i][j][kk]|=dp[k][j-1][kk];
    cout<<dijkstra(1,n)<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1613.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆