Asia EC Online 2025 (I)——Knapsack Problem · znzryb

## 思路讲解

还是比较简单，比较容易想到的。

## AC代码

[https://vjudge.net/solution/63500041](https://vjudge.net/solution/63500041)



::: 源代码

```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef _DEBUG
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e5+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT, V;

inline void __();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

//	cin>>lT;
//	while(lT--)
	__();
	return 0;
}
/*

*/
vector<arr2> g[MAXN];
struct Dis{
	ll knap, cur, u;
	bool operator<(const Dis & o)const{
		if (knap != o.knap) return knap > o.knap;
		return cur > o.cur;
	}
};
bool vis[MAXN];
ll dist[MAXN];
inline void __() {
	cin >> N >> M >> V >> T;
	priority_queue < Dis > pq;
	FOR(i, 1, M) {
		int u, v;
		ll w;
		cin >> u >> v >> w;
		g[u].PB({v, w});
		g[v].PB({u, w});
	}
	FOR(i, 1, N) {
		dist[i] = -1;
	}
	pq.push({1, 0, T});
	while (!pq.empty()) {
		auto [knap, cur, u] = pq.top();
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		dist[u] = knap;
		for (auto&[v, w] : g[u]) {
			if (cur + w > V) {
				// 包 与 包之间不能装东西
				// pq.push({knap+1,cur+w-V,v}); 所以这个写法是错的
				pq.push({knap + 1, w, v});
			} else {
				pq.push({knap, cur + w, v});
			}
		}
	}
	FOR(i, 1, N) {
		cout << dist[i] << " ";
	}
	cout << "\n";
}
/*
AC
https://vjudge.net/solution/63500041
*/
```


:::


## 心路历程（WA，TLE，MLE……）