}
//没有这个if就会出现后面的耗费比前面多，但实际获得的价值都一样
if (j && dp[tp][j] == dp[tp][j-1])
power[tp][j] = min(power[tp][j],power[tp][j-1]);
}
for (j = cost[tp]; j <= m; ++j) {
//完全背包
if (dp[tp][j] < dp[tp][j-cost[tp]]+val[tp]) {
dp[tp][j] = dp[tp][j-cost[tp]] + val[tp];
power[tp][j] = power[tp][j-cost[tp]];
}
else if(dp[tp][j] == dp[tp][j-cost[tp]]+val[tp])
power[tp][j] = min(power[tp][j],power[tp][j-cost[tp]]);
}
for (j = 0; j <= m; ++j) {
//更新答案
if (dp[tp][j] > ans)
ans = dp[tp][j],dist = power[tp][j];
else if (dp[tp][j] == ans)
dist = min(dist,power[tp][j]);
}
//printf("cur %d:\n",cur.v),Debug_InPut();
}
}
int main()
{
int i,j,k,a,b,c;
while (~scanf("%d%d%d%d",&n,&road,&m,&x)) {
Initial(); www.2cto.com
for (i = 1; i <= n; ++i)
scanf("%d%d",&cost[i],&val[i]);
for (i = 1; i <= road; ++i) {
scanf("%d%d%d",&a,&b,&c);
cnt[b]++;
cur.v = b,cur.len = c;
mmap[a].push_back(cur);
}
ToooPooo();
Solve_AC();
//printf("ans %lld %lld\n",ans,dist);
printf("%lld\n",dist);
}
}
作者：woshi250hua