本文共 1791 字，大约阅读时间需要 5 分钟。
为了解决这个问题，我们需要找到从城市1到城市n的最小费用路径。费用计算方式是：如果在路径中已经访问过某个特定城市，则费用为P，否则费用为R。我们可以使用广度优先搜索（BFS）结合状态压缩来解决这个问题。
方法思路
问题分析：我们需要从城市1到城市n，费用取决于是否在路径中已经访问过某个特定城市。这个问题可以通过状态压缩的广度优先搜索来解决。 状态表示：使用一个整数mask来表示已访问的城市集合，其中每一位表示对应的城市是否被访问过。 费用计算：对于每条路，检查mask中的特定位是否为1，来决定费用是P还是R。 记忆化搜索：记录到达每个城市和每个mask状态时的最小费用，避免重复计算。 解决代码
#include #include #include #include using namespace std;int main() { int n, m; vector > edges; // edges[p]存储从p出发的所有路的信息 // 读取输入 scanf("%d%d", &n, &m); for (int p = 1; p <= m; p++) { int v, c, P, R; scanf("%d%d%d%d", &v, &c, &P, &R); edges[p].push_back({v, c, P, R}); } // 初始化记忆化数组 vector memo[n+1][1 << n]; queue > q; // 起点是城市1，已访问过，费用为0 memo[1][1 << 0] = 0; q.push({1, 1 << 0, 0}); int ans = INT_MAX; while (!q.empty()) { auto current = q.front(); q.pop(); int u = current.first; int mask = current.second; int cost = current.third; // 如果到达终点，更新答案 if (u == n) { if (cost < ans) ans = cost; continue; } // 遍历所有从u出发的路 for (auto& edge : edges[u]) { int v = edge[0]; // 下一个城市 int c = edge[1]; // 需要检查的城市 int P = edge[2]; // P费用 int R = edge[3]; // R费用 // 计算费用 if (mask & (1 << (c-1))) { int fee = P; new_cost = cost + fee; } else { int fee = R; new_cost = cost + fee; } int new_mask = mask | (1 << (v-1)); if (new_cost < memo[v][new_mask]) { memo[v][new_mask] = new_cost; q.push({v, new_mask, new_cost}); } } } if (ans != INT_MAX) { printf("%d", ans); } else { puts("impossible"); } return 0;}
代码解释
输入处理：读取城市数n和路数m，然后读取每条路的信息，存储在edges数组中。 初始化：使用一个二维数组memo记录到达每个城市和每个mask状态时的最小费用。起点城市1已访问，费用为0。 广度优先搜索：使用队列处理每个状态，检查从当前城市出发的所有路，计算费用并更新状态。 费用计算：根据mask检查是否已经访问过特定城市，决定费用为P或R，更新新的mask状态。 记忆化：避免重复计算，记录到达每个状态的最小费用，继续处理下一个状态。 通过这种方法，我们可以高效地找到从城市1到城市n的最小费用路径。
转载地址：http://tfxfk.baihongyu.com/