C20220806T1 暴力计算

给定一张图，按照边权走，求总边权达到 \(M\) 时用的最短长度。 \(n\leq 100,M\leq 10^{18}\) 。

首先可以用 \(dp[i][j][k]\) 表示从 \(i\) 出发通过 \(2^k\) 步走到 \(j\) 能产生的最大价值。 那么有 \(dp[i][j][k]=\max\{dp[i][x][k-1]+dp[x][j][k-1]\}\) ，可以用floyd来转移，然后再反向跳 \(dp\) 数组即可得到答案。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp std::make_pair
#define pii std::pair<int,int>
#define chkmin(_A,_B) (_A=std::min(_A,_B))
#define chkmax(_A,_B) (_A=std::max(_A,_B))
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define copy(x,t) memcpy(x,t,sizeof(x))
//--------------------FastInOut--------------------//
class IO{
    public:
        inline char read(){
            static const int IN_LEN =1<<18|1;
            static char buf[IN_LEN],*s,*t;
            return (s==t)&&(t=(s=buf)+fread(buf, 1, IN_LEN, stdin)),(s==t)?-1:*s++;
        }
        template<typename _Tp>inline IO &operator >>(_Tp &x){
            static char c11, boo;
            for (c11=read(),boo=0;!isdigit(c11);c11=read()){
                if (c11==-1)
                    return *this;
                boo|=(c11=='-');
            }
            for(x=0;isdigit(c11);c11=read())
                x=x*10+(c11^'0');
            if(boo)
                x=-x;
            return *this;
        }
        inline void push(const char &c){
            putchar(c);
        }
        template<typename _Tp>inline IO &operator <<( _Tp x){
            if (x<0)
                x=-x,push('-');
            static _Tp sta[35];
            _Tp top=0;
            do{
                sta[top++]=x%10,x/=10;
            }while(x);
            while(top)
                push(sta[--top]+'0');
            return *this;
        }
        inline IO &operator <<(char lastChar){
            push(lastChar);
            return *this; 
        }
}FIO;
#define INF 1e18
ll f[65][205][205],rec[205],tmp[205];
ll T,n,m;
int main(){
    FIO>>T;
    while(T--){
        FIO>>n>>m;
        int r=0;
        ll ans=0;
        rep(i,1,n) rep(j,1,n){
            FIO>>f[0][i][j];
            f[0][i][j]=(!f[0][i][j])?-INF:f[0][i][j];
         }
        rep(w,1,60){
            rep(i,1,n) rep(j,1,n){
                f[w][i][j]=-INF;
                rep(k,1,n) f[w][i][j]=std:: max(f[w][i][j],f[w-1][i][k]+f[w-1][k][j]);
             }
            bool flag=false;
            rep(i,1,n) if (f[w][1][i]>=m){
                flag=true; break;
             }
            if (flag){
                r=w; break;
             }
         }
        rep(i,1,n) rec[i]=f[r-1][1][i];
        ans+=(ll)(1ll<<(r-1));
        drp(w,r-2,0){
            rep(i,1,n){ tmp[i]=-INF;
                rep(j,1,n){
                    tmp[i]=std:: max(tmp[i],rec[j]+f[w][j][i]);
                 }
             }
            bool flag=true;
            rep(i,1,n) if (tmp[i]>=m) flag=false;
            if (flag){
                copy(rec,tmp);
                ans+=(ll)(1ll<<w);
             }
         }
         FIO<<ans+1<<'\n';
     }
    return 0;
}