企业官网建设流程全解析

题目链接：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 = pair<int, int>; const int N = 1e5 + 5; const int INF = 1e9; int n, m, V, T; vector<Pair> 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_queue<State> 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(d>dist[u]){ continue; } if(d==dist[u]&&r<rem[u]){ continue; } for(auto &edge:G[u]){ int v = edge.first;//邻接点 int w = edge.second;//边权（物品重量） int nd, nr;//新的状态：背包数、剩余容量 if(r>=w){ //情况1：当前背包剩余容量足够装下这个物品 //不需要换背包，背包数不变，剩余容量减少 nd = d; nr = r - w; }else{ //情况2：当前背包容量不够 //必须换一个新背包(丢弃旧背包) nd = d + 1; nr = V - w; } //更新最优解 //判读条件： //1.新状态的背包数更少->更新 //2.背包数相同，但剩余容量更大->更新（因为更大剩余容量对未来更有利 if(nd<dist[v]||(nd==dist[v])&&nr>rem[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 t=1; //cin >> T; while (t--) { solve(); } return 0; }