LOJ #539「LibreOJ NOIP Round #1」旅游路线

T 城是一个旅游城市，具有n个景点和m条道路，所有景点编号为 1,2,…,n。每条道路连接这n个景区中的某两个景区，道路是单向通行的。每条道路都有一个长度。

为了方便旅游，每个景点都有一个加油站。第i个景点的加油站的费用为 pi,加油量为ci。若汽车在第i个景点加油，则需要花费pi元钱，之后车的油量将被加至油量上限与ci中的较小值。不过如果加油前汽车油量已经不小于 ci，则不能在该景点加油。

小 C 准备来到 T 城旅游。他的汽车油量上限为 C。旅游开始时，汽车的油量为0。在旅游过程中：

1、当汽车油量大于0 时，汽车可以沿从当前景区出发的任意一条道路到达另一个景点（不能只走道路的一部分），汽车油量将减少1；

2、当汽车在景点i且当前油量小于ci时，汽车可以在当前景点加油，加油需花费pi元钱，这样汽车油量将变为 min{ci,C}。

一次旅游的总花费等于每次加油的花费之和，旅游的总路程等于每次经过道路的长度之和。注意多次在同一景点加油，费用也要计算多次，同样地，多次经过同一条道路，路程也要计算多次。

小 C 计划旅游 T 次，每次旅游前，小 C 都指定了该次旅游的起点和目标路程。由于行程不同，每次出发前带的钱也不同。为了省钱，小 C 需要在旅游前先规划好旅游路线（包括旅游的路径和加油的方案），使得从起点出发，按照该旅游路线旅游结束后总路程不小于目标路程，且剩下的钱尽可能多。请你规划最优旅游路线，计算这 T 次旅游每次结束后最多可以剩下多少钱。

最后T行，每行包含三个正整数 si,qi,di，描述一次旅游计划，旅游的起点为编号为si的景点，出发时带了 qi元钱，目标路程为di

> 2<=n<=100 , 1<=m<=1000 , 1<=C,T<=1e5,pi,ci<=1e5,qi

根据T的规模，可知应该是预处理一下然后O(1)或者O(logn)回答询问，O(1)就是直接回答或者ST表，O(logn)就是线段树、倍增之类。

我们很不容易想到，用G[i][j]表示以i为起点带j元钱能行驶的最远路程记下，然后每次在G[i]中二分一个大于Di的且j最小的答案的答案

状态转移方程：G[i][j]=max{G[i][j-p[i]]+F[i][k]};

其中F[i][j]表示的是从i到j，加一次油能够行驶最远的路程

设 P[i][j][k]=max{F[e]][j][k-1]+l(e))};

其中P[i][j][k] 表示的是从i到j，经过k条边能够行驶最远的路程

其中e是i指向的城市，l(e)是这条边的路程

考虑优化，P[i][j][k]表示从i到j，经过2^j^条边能够行驶的最远距离

P[i][j][s]=max{P[i][k][s-1],P[k][j][s-1]}

然后将C[i]分解为每个2进制，后相加即可

详细题解

CODE:

#include<bits/stdc++.h>
const int N = 105;
const int inf = 0x3f3f3f3f;
int n,m,C,T,A[N],B[N];
int G[N][N][21],p[N],c[N]; 
int DP[N][N*N],D[N][N];
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*flag;
}
int main(){
    n=read(),m=read(),C=read(),T=read(); 
    for(int i=1;i<=n;++i){
        p[i]=read(),c[i]=read();
        c[i]=std::min(c[i],C);
        for(int j=1;j<=n;++j){
            G[i][j][0]=i==j?0:-inf;
        }
    }
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),c=read();
        G[a][b][0]=std::max(G[a][b][0],c);
    }
    for(int k=1;k<=20;++k){
        for(int a=1;a<=n;++a){
            for(int b=1;b<=n;++b){
                G[a][b][k]=-inf;
                for(int s=1;s<=n;++s){
                    G[a][b][k]=std::max(G[a][b][k],G[a][s][k-1]+G[s][b][k-1]);
                }
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            A[j]=i==j?0:-inf;
        for(int k=20;k+1;k--){
            if((c[i]>>k)&1){
                for(int j=1;j<=n;++j){
                    B[j]=-inf;
                    for(int d=1;d<=n;++d)
                        B[j]=std::max(B[j],A[d]+G[d][j][k]);
                }
                for(int j=1;j<=n;++j){
                    A[j]=B[j];
                }
            }
        }
        for(int j=1;j<=n;++j){
            D[i][j]=A[j];
        }
    }
    for(int i=0;i<=n*n;++i){
        for(int j=1;j<=n;++j){
            if(i>=p[j])
            for(int k=1;k<=n;++k)
                DP[j][i]=std::max(DP[j][i],DP[k][i-p[j]]+D[j][k]);
        }
    }
    while(T--){
        int s=read(),q=read(),d=read();
        int l=0,r=q+1;
        int ans=q+1;
        while(l+1<r){
            int mid=l+r>>1;
            if(DP[s][mid]>=d){
                ans=mid;
                r=mid;
            }
            else l=mid;
        }
        printf("%d\n",q-ans);
    }
}