标准\(noip\)题
Code #include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; using std::vector; const int N=105; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) int n,m,C,T; int mp[N][N]; int p[N],c[N]; int f[N][N*N]; int val[N][N]; int w[N],sy[N]; int g[N][N][21]; int getint(){ int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } signed main(){ n=getint(),m=getint(),C=getint(),T=getint(); for(int i=1;i<=n;i++){ p[i]=getint(); c[i]=getint(); c[i]=min(c[i],C); } memset(g,0xcf,sizeof g); for(int i=1;i<=n;i++) g[i][i][0]=0; for(int i=1;i<=m;i++){ int x=getint(),y=getint(),z=getint(); g[x][y][0]=max(g[x][y][0],z); } for(int p=1;(1<<p)<=C;p++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++) g[i][j][p]=max(g[i][j][p],g[i][k][p-1]+g[k][j][p-1]); } } } for(int x=1;x<=n;x++){ memset(w,0xcf,sizeof w);w[x]=0; for(int i=0;(1<<i)<=c[x];i++){ if(c[x]>>i&1){ memcpy(sy,w,sizeof w); for(int j=1;j<=n;j++) for(int p=1;p<=n;p++) sy[j]=max(sy[j],w[p]+g[p][j][i]); memcpy(w,sy,sizeof sy); } } memcpy(val[x],w,sizeof w); } for(int i=0;i<=n*n;i++){ for(int x=1;x<=n;x++){ if(i>=p[x]){ for(int j=1;j<=n;j++) f[x][i]=max(f[x][i],f[j][i-p[x]]+val[x][j]); } } } while(T--){ int s=getint(),q=getint(),d=getint(); int l=0,r=q,ans=q+1; while(l<=r){ int mid=l+r>>1; if(f[s][mid]>=d) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",max(-1,q-ans)); } return 0; }