题解 | # MeUmy吃海底捞#

实际上我们读题后会发现 就是在家到海底捞的最短路 然后拿最短路权值*2 然后去跑二进制多重背包 跑出痛苦值上限内的最大评分 然后找评分最大的情况下 最小痛苦值是多少 我们这里比较好玩的是给出的点和边不是0-N-1的编号 而是≤ 的 所以我们存边的时候需要 map 或者手写离散化 我是写的map的.

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
struct lb {
	long long int next;
	long long int top;
	long long int v;
}qxx[1000000];
struct qz
{
	long long int qz;
	long long int d;
	bool operator<(const struct qz& x)const {
		return qz > x.qz;
	}
};
priority_queue<qz>dl;
long long int n, m, q, lbys, H, K, T, hdlb[1000000], sl, KUP;
unordered_map<long long int, long long int>bt;
unordered_map<long long int, long long int>vis;
unordered_map<long long int, long long int>hx;
unordered_map<long long int, long long int>hdl;
void lj(long long int qd, long long int zd, long long int qz)
{
	qxx[++lbys].next = bt[qd];
	qxx[lbys].top = zd;
	qxx[lbys].v = qz;
	bt[qd] = lbys;
}
vector<long long int>t, w, zzq;
long long int dp[110000], hdlcs[110000];
int main() {
	//freopen("12.in", " r ", stdin);
    //freopen("9.out", " w ", stdout);
	cin >> n >> m >> q >> H >> K >> KUP;
	if (n > 1e5)return -1;
	if (m > 2*1e5)return -1;
	if (q > 1e18)return -1;
	if (H > 2000)return -1;
	if (K > 1e5)return -1;
	if (KUP > 1e4)return -1;
	for (long long int i = 1; i <= H; i++)
	{
		cin >> hdlb[i];
		if (hdlb[i] > 1e18)return -1;
	}
	for (long long int i = 1; i <= H; i++)
	{
		long long int qzcc;
		cin >> qzcc;
		hdl[hdlb[i]] = qzcc;
		if (qzcc > 1e9)return -2;
	}
	for (long long int i = 1; i <= H; i++)
	{
		cin >> hdlcs[i];
		if (hdlcs[i] > 2000)return -3;
	}

	vis[q] = 0;
	for (long long int i = 0; i < m; i++)
	{
		long long int qd, zd, qz;
		cin >> qd >> zd >> qz;
		if (qd > 1e18)return -1;
		if (zd > 1e18)return -1;
		if (qz > 1e5)return -1;
		lj(qd, zd, qz);
		lj(zd, qd, qz);
		if (vis[qd] == 0 && qd != q)
		{
			vis[qd] = 1e9;
		}
		if (vis[zd] == 0 && zd != q)
		{
			vis[zd] = 1e9;
		}
	}
	dl.push(qz{ 0,q });
	
	while (dl.size() != 0)
	{
		struct qz dz = dl.top(); dl.pop();
		if (hx.find(dz.d) != hx.end())continue;
		hx[dz.d] = 1;
		for (long long int i = bt[dz.d]; i != 0; i = qxx[i].next)
		{
			if (vis[qxx[i].top] > vis[dz.d] + qxx[i].v)
			{
				vis[qxx[i].top] = vis[dz.d] + qxx[i].v;
				if (hx.find(qxx[i].top) == hx.end())
					dl.push(qz{ vis[qxx[i].top],qxx[i].top });
			}
		}
	}
	for (long long int i = 1; i <= H; i++)
	{
		long long int sl = hdlcs[i];
		if (vis.find(hdlb[i]) == vis.end())continue;
		if (vis[hdlb[i]] == 1e9)continue;
		for (int j = 1; j <= sl; j *= 2)
		{
			sl -= j;
			t.push_back(j * (vis[hdlb[i]] * 2) * K);
			w.push_back(j * hdl[hdlb[i]]);
		}
		if (sl > 0)
		{
			t.push_back(sl * (vis[hdlb[i]] * 2) * K);
			w.push_back(sl * hdl[hdlb[i]]);
		}
	}

	for (long long int i = 0; i < t.size(); i++)
	{
		for (long long int j = KUP; j >= t[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
		}
	}

	long long int num = 0, sum = 0;
	for (long long int j = 0; j <= KUP; j++)
	{
		sum = max(sum, dp[j]);
	}
	for (long long int j = 0; j <= KUP; j++)
	{
		if (sum == dp[j])
		{
			num = j;
			break;
		}
	}
	if (sum == 0 && num == 0)
	{
		cout << -1;
		return 0;
	}
	cout << sum << endl << num;
	return 0;
}