列表

详情

NC222801. MeUmy吃海底捞

描述

呜米与咩栗很喜欢吃海底捞，这一天她们两个得到了一份地图。
这份地图上有N个标识点，以及M条路，连接着这N个标注点（不一定每个标注点都有和其他标注点相连的路线）。（出题人没见过只能单向的路）
每个标注点都有着一个独有的数字标识。
当然这份地图珍贵在于，地图上标注了全城所有的海底捞共H个。并且给出了每家店的评分。
呜米与咩栗的家的数字标识为SM。
每家店总有吃腻的一天，所以咩栗给出了她希望的每家店最多可以去的次数CS，并且每吃一次，都要回家一次。
因为众所周知的原因，呜米是光脚出门的，并且每走一米产生痛苦值K。
咩栗想要知道在呜米喵可以承受的最大痛苦值总和KUP内，可以吃到的海底捞的评分和最大是多少？
因为咩栗是钢板不会这个问题。所以她吧所有的数据整理成了一下，向你们求助。
注意:如果不存在能够在痛苦值上限KUP内到达的店铺 请输出-1
（出题人没见过只能单向的路）

输入描述

第一行 六个整数 N M SM H K KUP 对应上文
          
第二行 H个整数 代表了所有为海底捞的数字标识Z。
第三行 H个整数 为对应了第二行同位置的海底捞的评分W。
第四行 H个整数 为对应了第二行同位置的海底捞的最多可去次数CS。

以下M行 每行三个整数表示了 A标识点 到 B标识点 有一条长为C的路 (A与B给出的都是上文提到的数字标识)
 

输出描述

输出两行
第一行 吃过的海底捞评分的和的最高值
第二行 呜米在海底捞评分的和的最高值的情况下，产生的痛苦值最小是多少

如果不存在能够在痛苦值上限KUP内到达的店铺 请输出-1

示例1

输入: 

4 6 1 2 1 120
3 2
9 9
1 5
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出: 

54
28

示例2

输入: 

4 6 1 2 1 7
3 2
9 9
1 5
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出: 

9
4

示例3

输入: 

4 6 10 2 1 700
3 2
9 9
1 5
10 2 22
2 3 26
2 4 10
10 3 58
3 4 34
10 4 466

输出: 

54
316

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 351ms, 内存消耗: 38052K, 提交时间: 2021-06-27 17:31:39 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

class pack{
	public:
	ll n,m,dp[10050],g[10050],q[10050],v[10050],w[10050],s[10050];
	ll W[1000050],V[1000050];
	int index=0;
	void work() {
		for (int i = 1; i <= n; i++) {
			int c = 1;
			ll p,h,k;
			k=s[i];
			p=v[i];
			h=w[i];
			if(v[i]>m){continue;}
			while (k - c > 0) {
				k -= c;
			    W[++index]= c * p;
			    V[index]= c * h;
			    c *= 2;
			}
		  	W[++index]= p * k;
		  	V[index]= h * k;
		}
		for(int i=1;i<=index;i++){
			for(int j=m;j>=W[i];j--){
				dp[j]=max(dp[j],dp[j-W[i]]+V[i]);
			}
		}
		if(!dp[m]){puts("-1");exit(0);}
		for(int i=0;;i++){
			if(dp[i]==dp[m]){
				printf("%lld\n%d\n",dp[i],i);exit(0);
			}
		}
    }
}pk;

int i,j,k,n,m,t,kk,kup,it;
ll st,sb,x,y;
unordered_map<ll,ll> id,vis;
unordered_map<ll,vector<pair<ll,ll> > >v;
priority_queue<pair<ll,ll> >q;

int main(){
	memset(pk.v,1,sizeof(pk.v));
	scanf("%*d%d%lld%d%d%d",&m,&st,&n,&kk,&pk.m);
	for(i=1;i<=n;i++){
		scanf("%lld",&sb);
		id[sb]=i;
	}
	for(i=1;i<=n;i++){
		scanf("%lld",&pk.w[i]);
	}
	for(i=1;i<=n;i++){
		scanf("%lld",&pk.s[i]);
	}
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&sb);
		v[x].push_back({y,sb});
		v[y].push_back({x,sb});
	}
	q.push({0,st});
	while(!q.empty()){
		auto [x,y]=q.top();q.pop();
		if(vis[y]){continue;}vis[y]=1;
		if(id[y]){
			pk.v[id[y]]=-x*2*kk;
		}
		for(auto [i,j]:v[y]){
			if(vis[i]){continue;}
			q.push({x-j,i});
		}
	}
	pk.n=n;
	pk.work();
}

上一题

© 2024 nowcoder.com