题目链接Knapsack Problem - 题目 - QOJ.ac题目大意在无向图上从每个点出发到终点 T在背包容量限制下求最少换背包次数初始背包算1个。题目思路反向跑 Dijkstra状态为节点背包数剩余容量求每个点到 T 的最少背包数。代码如下#include bits/stdc.h using namespace std; // using i128 __int128; // #define int long long #define endl \n using Pair pairint, int; const int N 1e5 5; const int INF 1e9; int n, m, V, T; vectorPair G[N];//邻接表first邻接点second边权 /* 状态结构体 node当前节点 bags到达该节点已经用了多少个书包 rem当前背包剩余的容量 优先队列排序规则 1.优先比较bags(背包越少越好 2.bags相同时比较rem(剩余容量越大越好) */ struct State{ int node; int bags; int rem; bool operator(const State other)const{ if(bags!other.bags){ return bags other.bags;//bags小的优先 } return rem other.rem;//rem大的优先 } }; int dist[N];//dist[i]:从i到T所需的最少背包数 int rem[N];//rem[i]:在达到dist[i]这个最优值时能获得的最大剩余容量 void dijkstra(){ for (int i 1; i n;i){ dist[i] INF; // 初始化为无穷大 rem[i] -1;//-1表示为访问 } //从终点T出发(反向思考) //在T点我们假设已经用了1个背包剩余容量为V //为什么是1因为从起点出发时就需要一个背包来装东西 dist[T] 1; rem[T] V; //优先队列State按bags升序rem降序 priority_queueState pq; pq.push({T, dist[T], rem[T]}); while(!pq.empty()){ //取出当前最优状态 State cur pq.top(); pq.pop(); int u cur.node;//当前节点 int d cur.bags;//当前背包数 int r cur.rem;//当前剩余容量 //如果这个状态不是最优状态已经被更新过了跳过 //这是Dijkstra的标准优化避免处理过时状态 if(ddist[u]){ continue; } if(ddist[u]rrem[u]){ continue; } for(auto edge:G[u]){ int v edge.first;//邻接点 int w edge.second;//边权物品重量 int nd, nr;//新的状态背包数、剩余容量 if(rw){ //情况1当前背包剩余容量足够装下这个物品 //不需要换背包背包数不变剩余容量减少 nd d; nr r - w; }else{ //情况2当前背包容量不够 //必须换一个新背包(丢弃旧背包) nd d 1; nr V - w; } //更新最优解 //判读条件 //1.新状态的背包数更少-更新 //2.背包数相同但剩余容量更大-更新因为更大剩余容量对未来更有利 if(nddist[v]||(nddist[v])nrrem[v]){ dist[v] nd;//更新最少背包数 rem[v] nr;//更新最大剩余容量 pq.push({v, nd, nr});//将新状态加入优先队列 } } } } void solve() { cin n m V T; for (int i 0; i m;i){ int u, v, w; cin u v w; G[u].push_back({v, w}); G[v].push_back({u, w});//无向图需要双向加边 } dijkstra(); for (int i 1; i n;i){ if(dist[i]INF){ cout -1 ;//无法到达T }else{ cout dist[i] ;//输出最少背包数 } } cout endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t1; //cin T; while (t--) { solve(); } return 0; }