团体程序设计天梯赛-练习集 L2-036 网红点打卡攻略

L2-036 网红点打卡攻略 - 团体程序设计天梯赛-练习集

一、题目核心分析

有效路径的 3 个必要条件（缺一不可）

1. 路径长度（节点个数）必须等于n：因为要遍历n个城市（0~n-1）各一次，路径节点数恰好是n（最后返回 0 是额外的边，不是路径节点）。
2. 路径经过的节点必须是0~n-1的完整集合（无重复、无遗漏）：可以用哈希集合（unordered_set）去重，判断集合大小是否等于n。
3. 路径中相邻节点（包括路径最后一个节点和 0）之间必须存在有效道路（费用不为 - 1）：题目中用arr[a][b] = -1表示a和b之间无道路。

解题思路

1. 数据存储：用二维数组arr[N][N]存储两个城市之间的道路费用，初始化所有值为 - 1（表示无道路），输入道路信息时更新双向道路的费用。
2. 路径校验与费用计算：编写辅助函数get_money，对每条查询路径进行 3 个条件的校验，校验通过则计算总费用，否则返回 - 1。
3. 结果统计：遍历所有k条查询路径，统计有效路径数量cnt，同时记录最少费用minn和对应的路径编号id。
4. 输出结果：按要求打印有效路径数量、最少费用路径的编号和最少费用。

二、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核心逻辑

这是本题的核心，负责完成路径校验和费用计算，步骤如下：

1. 先判断路径长度是否为n，不满足直接返回 - 1（快速剪枝，减少后续计算）。
2. 遍历路径节点，逐个校验相邻节点是否有有效道路，同时累加费用、将节点加入去重集合。
3. 遍历结束后，校验两个关键条件：路径节点是否完整（集合大小为n）、最后一个节点能否返回起点 0。
4. 所有条件满足则累加返回起点的费用，返回总费用；否则返回 - 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. 第 1 条路径0->1->2->3->0：有效，总费用1+4+6+3=14（此处为示例计算，具体以实际输入为准）。
2. 第 2 条路径包含重复节点 0，无效。
3. 第 3 条路径0->1->3->2->0：有效，总费用1+5+6+2=14（示例）。
4. 最终有效路径数为 2，两条路径费用相同，取编号较小的 1。

总结

1. 本题核心是校验有效环游路径的 3 个必要条件，缺一不可，辅助函数get_money是实现该逻辑的关键。
2. 数据存储采用二维数组，道路双向赋值，结果统计需关注路径编号和最少费用的更新逻辑。
3. 解题时需注意细节（如返回起点 0、路径长度、双向道路），这些是避免出错的核心要点。

易错点提醒

• 忘记道路是双向的，只赋值arr[a][b] = c，未赋值arr[b][a] = c，导致反向路径判断错误。
• 忽略路径最后一个节点需要返回起点 0，漏判arr[u][0] == -1，导致无效路径被误判为有效。
• 路径长度判断错误：将 “返回起点 0” 算作路径节点，误判路径长度应为n+1，实际题目中路径节点只需要包含n个城市各一次。
• 初始化minn时使用过大的值（如INT_MAX），导致累加费用后溢出，推荐使用0x3f3f3f3f。