LP1613 跑路

Problem

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

Solution

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

令dp[i][j][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://acxblog.site/archives/sol-luogu-1613.html
本文采用 CC BY-NC-SA 3.0 协议进行许可