description
题面较长，这里给出题目链接
solution
考虑预处理出
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示在第
i
i
i个点加满油后，从第
i
i
i个点出发，至多消耗
j
j
j元钱走过的最大路程，那么对于每一个询问就可以二分答案
O
(
l
o
g
q
)
O(logq)
O(logq)查询了可以得出转移方程
f
[
i
]
[
k
]
=
max
(
f
[
j
]
[
k
−
p
[
j
]
]
+
g
[
i
]
[
j
]
,
f
[
i
]
[
k
]
)
f[i][k]=\max(f[j][k-p[j]]+g[i][j],f[i][k])
f[i][k]=max(f[j][k−p[j]]+g[i][j],f[i][k])，其中
g
[
i
]
[
j
]
g[i][j]
g[i][j]表示从在
i
i
i点加满油后从
i
i
i走到
j
j
j能走过的最大路程
g
g
g可以使用倍增
f
l
o
y
d
floyd
floyd预处理出
h
[
k
]
[
i
]
[
j
]
h[k][i][j]
h[k][i][j]表示从
i
i
i走到
j
j
j,至多走
2
k
2^k
2k步的最长路程后求出。倍增
f
l
o
y
d
floyd
floyd代码：
for(int k=1;k<=16;++k){
memcpy(h[k],h[k-1],sizeof(h[k]));
for(int w=1;w<=n;++w)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(h[k-1][i][w]>inf&&h[k-1][w][j]) h[k][i][j]=max(h[k][i][j],h[k-1][i][w]+h[k-1][w][j]);
}
于是我们就可以
O
(
n
3
l
o
g
C
)
O(n^3logC)
O(n3logC)完成预处理，总时间复杂度
O
(
n
3
l
o
g
C
+
T
l
o
g
q
)
O(n^3logC+Tlogq)
O(n3logC+Tlogq)
code
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,C,T,p[N],c[N],b[N],inf;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int f[N][N*N];
int g[N][N];
int h[20][N][N];
int main(){
n=read();m=read();C=read();T=read();
for(int i=1;i<=n;++i) p[i]=read(),c[i]=read();
memset(h,192,sizeof(h));inf=h[0][0][0];
for(int i=1;i<=n;++i) h[0][i][i]=0;
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
h[0][u][v]=max(h[0][u][v],w);
}
for(int k=1;k<=16;++k){
memcpy(h[k],h[k-1],sizeof(h[k]));
for(int w=1;w<=n;++w)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(h[k-1][i][w]>inf&&h[k-1][w][j]) h[k][i][j]=max(h[k][i][j],h[k-1][i][w]+h[k-1][w][j]);
}
for(int i=1;i<=n;++i){
memset(g[i],192,sizeof(g[i]));g[i][i]=0;
int s=min(C,c[i]);
for(int k=0;k<=16;++k){
if((s>>k)&1){
memset(b,inf,sizeof(b));
for(int j=1;j<=n;++j){
if(g[i][j]>inf){
for(int w=1;w<=n;++w)
if(h[k][j][w]>inf) b[w]=max(b[w],g[i][j]+h[k][j][w]);
}
}
memcpy(g[i],b,sizeof(b));
}
}
}
for(int k=0;k<=n*n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][k]=max(f[i][k],g[i][j]);
for(int k=0;k<=n*n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(k>=p[j]) f[i][k]=max(f[i][k],f[j][k-p[j]]+g[i][j]);
while(T--){
int u=read(),q=read(),d=read();
int l=p[u],r=q;
while(l<r){
int mid=(l+r)>>1;
if(f[u][mid-p[u]]>=d) r=mid;
else l=mid+1;
}
if(f[u][l-p[u]]<d) puts("-1");
else printf("%d\n",q-l);
}
return 0;
}
Processed:
0.019, SQL:
8
