L2-036 网红点打卡攻略 - 团体程序设计天梯赛-练习集
一、题目核心分析
有效路径的 3 个必要条件（缺一不可）
- 路径长度（节点个数）必须等于
n：因为要遍历n个城市（0~n-1）各一次，路径节点数恰好是n（最后返回 0 是额外的边，不是路径节点）。 - 路径经过的节点必须是
0~n-1的完整集合（无重复、无遗漏）：可以用哈希集合（unordered_set）去重，判断集合大小是否等于n。 - 路径中相邻节点（包括路径最后一个节点和 0）之间必须存在有效道路（费用不为 - 1）：题目中用
arr[a][b] = -1表示a和b之间无道路。
解题思路
- 数据存储：用二维数组
arr[N][N]存储两个城市之间的道路费用，初始化所有值为 - 1（表示无道路），输入道路信息时更新双向道路的费用。 - 路径校验与费用计算：编写辅助函数
get_money，对每条查询路径进行 3 个条件的校验，校验通过则计算总费用，否则返回 - 1。 - 结果统计：遍历所有
k条查询路径，统计有效路径数量cnt，同时记录最少费用minn和对应的路径编号id。 - 输出结果：按要求打印有效路径数量、最少费用路径的编号和最少费用。
二、AC代码（带详细注释）
#include<bits/stdc++.h> using namespace std; const int N = 205; // 题目中城市数量的上限，设置205足够满足需求 int arr[N][N]; // 存储两个城市之间的道路费用，arr[a][b]表示a到b的费用，-1表示无道路 int cnt = 0; // 符合条件的有效路径数 int minn = 0x3f3f3f3f; // 记录最少费用，初始化为一个极大值（0x3f3f3f3f是常用的极大值，不会溢出） int id = 0; // 记录费用最少的有效路径的编号 int n, m; // n：城市总数，m：道路总数 /** * 辅助函数：校验路径是否有效，并计算有效路径的总费用 * @param len：查询路径的节点个数 * @param as：查询路径的节点列表 * @return：有效路径返回总费用，无效路径返回-1 */ int get_money(int len, const vector<int> &as) { // 条件1：路径节点个数必须等于n（遍历所有n个城市各一次） if (len != n) return -1; unordered_set<int> st; // 用于去重，判断路径是否包含所有城市 int u = 0; // 起点城市，固定为0 int ans = 0; // 记录路径总费用 for (int v : as) { // 条件2.1：当前节点u和下一个节点v之间无有效道路，路径无效 if (arr[u][v] == -1) return -1; st.insert(v); // 将节点v加入集合，用于后续去重判断 ans += arr[u][v]; // 累加道路费用 u = v; // 更新当前节点为v，继续遍历下一个节点 } // 条件2.2：路径包含的节点去重后大小不等于n（有重复或遗漏），路径无效 // 条件2.3：路径最后一个节点u无法返回起点0（无有效道路），路径无效 if (arr[u][0] == -1 || st.size() != n) return -1; ans += arr[u][0]; // 累加最后一个节点返回0的道路费用 return ans; // 返回有效路径的总费用 } int main() { // 初始化二维数组arr所有元素为-1，表示初始时所有城市之间无道路 memset(arr, -1, sizeof arr); cin >> n >> m; for (int i = 1; i <= m; ++i) { int a, b, c; cin >> a >> b >> c; // 题目中道路是双向的，因此双向更新费用 arr[a][b] = arr[b][a] = c; } int k; cin >> k; // k条查询路径 for (int i = 1; i <= k; ++i) { // 路径编号从1开始 int kk; cin >> kk; // 当前路径的节点个数 vector<int> list; // 存储当前路径的节点列表 for (int j = 0; j < kk; ++j) { int w; cin >> w; list.emplace_back(w); } // 调用辅助函数，获取当前路径的总费用（无效则为-1） int d = get_money(kk, list); if (d == -1) continue; // 路径无效，跳过后续统计 // 路径有效，更新统计信息 cnt++; // 有效路径数+1 // 更新最少费用和对应路径编号 if (d < minn) { minn = d; id = i; } } // 按题目要求输出结果 cout << cnt << endl; cout << id << ' ' << minn << endl; return 0; }三、关键模块解析
1. 初始化与数据存储
- 用
memset(arr, -1, sizeof arr)初始化二维数组：memset按字节赋值，由于-1的补码是全 1，因此可以正确将int类型的数组元素赋值为 - 1，快速标记所有城市之间初始无道路。 - 道路是双向的，因此输入
a b c时，需要同时赋值arr[a][b] = c和arr[b][a] = c，保证从a到b和从b到a的费用一致且有效。
2. 辅助函数get_money核心逻辑
这是本题的核心，负责完成路径校验和费用计算，步骤如下：
- 先判断路径长度是否为
n，不满足直接返回 - 1（快速剪枝，减少后续计算）。 - 遍历路径节点，逐个校验相邻节点是否有有效道路，同时累加费用、将节点加入去重集合。
- 遍历结束后，校验两个关键条件：路径节点是否完整（集合大小为
n）、最后一个节点能否返回起点 0。 - 所有条件满足则累加返回起点的费用，返回总费用；否则返回 - 1。
3. 结果统计与更新
- 有效路径数
cnt：只有当d != -1时，才进行cnt++。 - 最少费用
minn：初始化为0x3f3f3f3f（这是 C++ 中常用的极大值，约为 1e9，大于题目中可能的总费用，且不会出现整数溢出），当遇到更小的有效路径费用时，更新minn和对应的路径编号id。 - 路径编号：题目中查询路径从 1 开始编号，因此循环变量
i从 1 到k，直接用i作为路径编号即可。
四、运行结果说明
输入示例（简化版）
4 6 0 1 1 0 2 2 0 3 3 1 2 4 1 3 5 2 3 6 3 4 1 2 3 4 0 1 2 4 1 3 2输出示例
plaintext
2 1 10解释
- 第 1 条路径
0->1->2->3->0：有效，总费用1+4+6+3=14（此处为示例计算，具体以实际输入为准）。 - 第 2 条路径包含重复节点 0，无效。
- 第 3 条路径
0->1->3->2->0：有效，总费用1+5+6+2=14（示例）。 - 最终有效路径数为 2，两条路径费用相同，取编号较小的 1。
总结
- 本题核心是校验有效环游路径的 3 个必要条件，缺一不可，辅助函数
get_money是实现该逻辑的关键。 - 数据存储采用二维数组，道路双向赋值，结果统计需关注路径编号和最少费用的更新逻辑。
- 解题时需注意细节（如返回起点 0、路径长度、双向道路），这些是避免出错的核心要点。
易错点提醒
- 忘记道路是双向的，只赋值
arr[a][b] = c，未赋值arr[b][a] = c，导致反向路径判断错误。 - 忽略路径最后一个节点需要返回起点 0，漏判
arr[u][0] == -1，导致无效路径被误判为有效。 - 路径长度判断错误：将 “返回起点 0” 算作路径节点，误判路径长度应为
n+1，实际题目中路径节点只需要包含n个城市各一次。 - 初始化
minn时使用过大的值（如INT_MAX），导致累加费用后溢出，推荐使用0x3f3f3f3f。
