94. 城市间货物运输 I题目描述某国为促进城市间经济交流决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市通过道路网络连接网络中的道路仅允许从某个城市单向通行到另一个城市不能反向通行。网络中的道路都有各自的运输成本和政府补贴道路的权值计算方式为运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用权值为负则表示政府的补贴超过了支出的运输成本实际表现为运输过程中还能赚取一定的收益。请找出从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本。如果最低运输成本是一个负数它表示在遵循最优路径的情况下运输过程中反而能够实现盈利。城市 1 到城市 n 之间可能会出现没有路径的情况同时保证道路网络中不存在任何负权回路。输入描述第一行包含两个正整数第一个正整数 n 表示该国一共有 n 个城市第二个整数 m 表示这些城市中共有 m 条道路。接下来为 m 行每行包括三个整数s、t 和 v表示 s 号城市运输货物到达 t 号城市道路权值为 v 单向图。输出描述如果能够从城市 1 到连通到城市 n 请输出一个整数表示运输成本。如果该整数是负数则表示实现了盈利。如果从城市 1 没有路径可达城市 n请输出 unconnected。输入示例6 7 5 6 -2 1 2 1 5 3 1 2 5 2 2 4 -3 4 6 4 1 3 5输出示例1#include iostream #include vector #include queue using namespace std; // 表示一个较大的数作为“无穷大” const int INF 1e6; // 边结构体 struct Edge { int t; // 边的终点 int v; // 边的权值 Edge(int t, int v) : t(t), v(v) {} }; int main() { int n, m; cin n m; // n 表示点数m 表示边数 // 邻接表存图edges[i] 表示从点 i 出发的所有边 vectorvectorEdge edges(n 1); // 输入 m 条有向边 for (int i 0; i m; i) { int s, t, v; cin s t v; // s - t权值为 v edges[s].push_back(Edge(t, v)); } int start 1, end n; // 起点为 1终点为 n // minDist[i] 表示从起点到点 i 的最短距离 vectorint minDist(n 1, INF); // visited[i] 表示点 i 是否已经在队列中 // 注意这里的 visited 更准确地说应该叫 inQueue vectorbool visited(n 1, false); queueint que; // 初始化起点 que.push(start); minDist[start] 0; visited[start] true; // SPFA 算法主体 while (!que.empty()) { int cur que.front(); que.pop(); // 当前点出队标记为不在队列中 visited[cur] false; // 遍历当前点的所有出边 for (Edge edge : edges[cur]) { int s cur; // 当前起点 int t edge.t; // 边的终点 int v edge.v; // 边的权值 // 松弛操作 // 如果经过 s 到 t 的路径更短就更新 minDist[t] if (minDist[t] minDist[s] v) { minDist[t] minDist[s] v; // 如果 t 不在队列中就加入队列 if (!visited[t]) { que.push(t); visited[t] true; } } } } // 输出结果 if (minDist[end] INF) cout unconnected endl; else cout minDist[end] endl; return 0; }总结1. 算法简介这段代码实现的是 SPFA 算法用于求有向图中从1号点到n号点的最短路径。SPFA 可以看作是 Bellman-Ford 算法的队列优化版本。它的核心思想是如果某个点的最短距离被更新了那么从这个点出发的边也可能继续更新其他点所以把这个点放进队列中继续处理。2. 代码思路首先使用邻接表存图vectorvectorEdge edges(n 1);其中edges[s]存储所有从s出发的边。然后初始化距离数组vectorint minDist(n 1, INF); minDist[start] 0;表示起点到自己的距离是0到其他点的距离暂时认为是无穷大。接着从起点开始入队不断取出队首节点对它的所有出边进行松弛if (minDist[t] minDist[s] v) { minDist[t] minDist[s] v; }如果一个点的距离被更新并且它当前不在队列中就将它加入队列等待后续继续扩展。3. 变量说明minDist[i]表示从起点1到点i的最短距离。visited[i]表示点i当前是否在队列中。这里命名为visited容易误解更推荐改名为inQueue。queueint que用于存储需要继续松弛的节点。4. 算法特点SPFA 可以处理 负权边但不能处理 负权环。如果图中存在从起点可达的负权环最短路会不断变小算法可能无法正常结束。平均情况下 SPFA 表现不错但最坏情况下时间复杂度仍然可能退化到O(n * m)其中n是点数m是边数。95. 城市间货物运输 II题目描述某国为促进城市间经济交流决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市通过道路网络连接网络中的道路仅允许从某个城市单向通行到另一个城市不能反向通行。网络中的道路都有各自的运输成本和政府补贴道路的权值计算方式为运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用权值为负则表示政府的补贴超过了支出的运输成本实际表现为运输过程中还能赚取一定的收益。然而在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时存在一种情况图中可能出现负权回路。负权回路是指一系列道路的总权值为负这样的回路使得通过反复经过回路中的道路理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴算法还需检测这种特殊情况。请找出从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。城市 1 到城市 n 之间可能会出现没有路径的情况输入描述第一行包含两个正整数第一个正整数 n 表示该国一共有 n 个城市第二个整数 m 表示这些城市中共有 m 条道路。接下来为 m 行每行包括三个整数s、t 和 v表示 s 号城市运输货物到达 t 号城市道路权值为 v。输出描述如果没有发现负权回路则输出一个整数表示从城市1到城市n的最低运输成本包括政府补贴。如果该整数是负数则表示实现了盈利。如果发现了负权回路的存在则输出 circle。如果从城市 1 无法到达城市 n则输出 unconnected。输入示例4 4 1 2 -1 2 3 1 3 1 -1 3 4 1输出示例circle#include iostream #include vector #include queue using namespace std; // 定义一个较大的数表示无穷大 const int INF 1e6; // 边结构体 struct Edge { int t; // 边的终点 int v; // 边的权值 Edge(int t, int v) : t(t), v(v) {} }; int main() { int n, m; cin n m; // n 表示点数m 表示边数 // 使用邻接表存图 // edges[i] 表示从点 i 出发的所有边 vectorvectorEdge edges(n 1); // 输入 m 条有向边 for (int i 0; i m; i) { int s, t, v; cin s t v; // s - t权值为 v edges[s].push_back(Edge(t, v)); } int start 1, end n; // 起点为 1终点为 n bool flag true; // 用来标记是否存在负权环 // minDist[i] 表示从起点到点 i 的最短距离 vectorint minDist(n 1, INF); // visited[i] 表示点 i 当前是否在队列中 // 更准确的命名可以是 inQueue vectorbool visited(n 1, false); // count[i] 表示点 i 入队的次数 // 如果某个点入队次数达到 n说明存在负权环 vectorint count(n 1, 0); queueint que; // 初始化起点 que.push(start); minDist[start] 0; count[start] 1; // 建议加上这一句使 visited 的含义更加严谨 visited[start] true; // SPFA 算法主体 while (!que.empty()) { int cur que.front(); que.pop(); // 当前点出队标记为不在队列中 visited[cur] false; // 遍历当前点的所有出边 for (Edge edge : edges[cur]) { int s cur; // 当前点 int t edge.t; // 边的终点 int v edge.v; // 边的权值 // 松弛操作 // 如果从 s 到 t 可以得到更短距离就更新 minDist[t] if (minDist[t] minDist[s] v) { minDist[t] minDist[s] v; // 如果 t 当前不在队列中就加入队列 if (!visited[t]) { que.push(t); visited[t] true; // 记录 t 的入队次数 count[t]; // 如果某个点入队次数达到 n // 说明存在从起点可达的负权环 if (count[t] n) { flag false; // 清空队列提前结束算法 while (!que.empty()) que.pop(); break; } } } } } // 根据结果输出 if (!flag) cout circle endl; // 存在负权环 else if (minDist[end] INF) cout unconnected endl; // 起点无法到达终点 else cout minDist[end] endl; // 输出最短路径 return 0; }总结1. 算法简介这段代码实现的是 带负权环判断的 SPFA 算法。它不仅可以求从1号点到n号点的最短路径还可以判断从起点出发是否能够到达某个 负权环。如果存在负权环最短路径会被不断变小此时最短路没有实际意义程序输出circle2. 存图方式代码使用邻接表存储有向图vectorvectorEdge edges(n 1);其中edges[s]表示从点s出发的所有边。每条边用结构体Edge表示struct Edge { int t; int v; };t表示终点v表示边权。3. SPFA 核心思想SPFA 的核心是 松弛操作。如果当前点s到终点t可以得到更短路径就更新minDist[t]if (minDist[t] minDist[s] v) { minDist[t] minDist[s] v; }一旦某个点的最短距离被更新它后面的边也可能继续影响其他点所以需要将这个点加入队列继续处理。4. 队列优化代码中使用queueint存储需要继续处理的节点queueint que;同时用visited数组判断某个点是否已经在队列中vectorbool visited(n 1, false);这样可以避免同一个点重复入队提高效率。不过这里的visited更准确地说不是“访问过”而是“是否在队列中”所以命名为inQueue会更清晰。5. 负权环判断代码使用count[i]记录点i的入队次数vectorint count(n 1, 0);在一个没有负权环的图中最短路最多经过n - 1条边。如果某个点被反复更新并且入队次数达到n就说明存在负权环if (count[t] n) { flag false; }此时程序认为最短路不存在输出circle6. 总结这份代码是在普通 SPFA 的基础上加入了 入队次数统计从而实现了负权环判断。整体流程可以概括为建图 → 初始化距离 → 队列松弛 → 统计入队次数 → 判断负权环 → 输出结果96. 城市间货物运输 III题目描述某国为促进城市间经济交流决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市通过道路网络连接网络中的道路仅允许从某个城市单向通行到另一个城市不能反向通行。网络中的道路都有各自的运输成本和政府补贴道路的权值计算方式为运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用权值为负则表示政府的补贴超过了支出的运输成本实际表现为运输过程中还能赚取一定的收益。请计算在最多经过 k 个城市的条件下从城市 src 到城市 dst 的最低运输成本。输入描述第一行包含两个正整数第一个正整数 n 表示该国一共有 n 个城市第二个整数 m 表示这些城市中共有 m 条道路。接下来为 m 行每行包括三个整数s、t 和 v表示 s 号城市运输货物到达 t 号城市道路权值为 v。最后一行包含三个正整数src、dst、和 ksrc 和 dst 为城市编号从 src 到 dst 经过的城市数量限制。输出描述输出一个整数表示从城市 src 到城市 dst 的最低运输成本如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径则输出 unreachable表示不存在符合条件的运输方案。输入示例6 7 1 2 1 2 4 -3 2 5 2 1 3 5 3 5 1 4 6 4 5 6 -2 2 6 1输出示例0#include iostream #include vector using namespace std; // 定义一个较大的数表示无穷大 const int INF 1e8; int main() { int n, m; cin n m; // n 表示点数m 表示边数 // 使用边集数组存图 // 每条边格式为{起点, 终点, 权值} vectorvectorint edges; // 输入 m 条有向边 for (int i 0; i m; i) { int s, t, v; cin s t v; // s - t权值为 v edges.push_back({s, t, v}); } int src, dst, k; cin src dst k; // 起点、终点、最多经过 k 个中转点 // minDist[i] 表示从 src 到 i 的最短距离 vectorint minDist(n 1, INF); // minDist_copy 用来保存上一轮的最短距离 // 防止一轮中连续松弛导致经过的边数超过限制 vectorint minDist_copy(n 1); // 起点到自己的距离为 0 minDist[src] 0; // 最多经过 k 个中转点等价于最多经过 k 1 条边 for (int i 1; i k 1; i) { // 保存上一轮结果 minDist_copy minDist; // 遍历所有边进行松弛操作 for (auto edge : edges) { int s edge[0]; // 边的起点 int t edge[1]; // 边的终点 int v edge[2]; // 边的权值 // 只有上一轮中 s 可达才可以用 s 去更新 t if (minDist_copy[s] ! INF minDist[t] minDist_copy[s] v) { minDist[t] minDist_copy[s] v; } } } // 输出结果 if (minDist[dst] INF) cout unreachable endl; // 无法到达 else cout minDist[dst] endl; // 输出最短距离 return 0; }总结1. 算法简介这段代码使用的是 Bellman-Ford 算法的限制边数版本。它解决的问题是从src出发到达dst在最多经过k个中转点的情况下求最短路径。最多经过k个中转点等价于最多走k 1 条边所以代码中循环执行了k 1轮松弛。2. 存图方式代码使用边集数组存图vectorvectorint edges;每条边存成一个三元组{s, t, v}含义是从 s 到 t 有一条权值为 v 的有向边这种存图方式非常适合 Bellman-Ford因为 Bellman-Ford 每一轮都需要遍历所有边。3. 核心状态核心数组是vectorint minDist(n 1, INF);其中minDist[i] 表示从 src 到 i 的当前最短距离初始化时minDist[src] 0;表示起点到自己的距离为0其他点暂时不可达。4. 为什么需要 minDist_copy这段代码里最关键的是minDist_copy minDist;每一轮松弛时都使用上一轮的minDist_copy来更新当前的minDist。这样做是为了限制路径使用的边数。如果不用minDist_copy那么在同一轮循环中一个刚刚被更新的点可能立刻继续更新其他点导致一轮内走了多条边从而破坏k 1条边的限制。5. 松弛操作核心松弛逻辑是if (minDist_copy[s] ! INF minDist[t] minDist_copy[s] v) { minDist[t] minDist_copy[s] v; }意思是如果上一轮中src可以到达s并且通过s - t可以让到达t的距离更短那么就更新minDist[t]。这就是 Bellman-Ford 的核心思想。6. 复杂度分析外层循环执行k 1次每次遍历所有边。所以时间复杂度是O((k 1) * m)空间复杂度主要来自距离数组和边集数组O(n m)7. 总结这段代码可以概括为边集存图 → 初始化距离 → 限制 k 1 轮松弛 → 判断终点是否可达