L2-036 网红点打卡攻略

题目 L2-036 网红点打卡攻略

思路分析

代码实现

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

using ll = long long;

using ull = unsigned long long;

using PII = pair<int, int>;

using Pll = pair<ll, ll>;

int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };

const int inf = 0x3f3f3f3f;

const int N=210;

int cost[N][N]; // 两点间的最小花费

int n, m;

signed main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i <= n; ++i) {

		for (int j = 0; j <= n; ++j) {

			cost[i][j] = inf;

		}

	}

	for (int i = 0; i < m; ++i) {

		int u, v, w;

		cin >> u >> v >> w;

		cost[u][v] = cost[v][u] = w;

	}

	int k; // 待检查攻略的数量

	cin >> k;

	int validPlanCount = 0;       // 合法攻略的数量

	int minCost = inf;            // 最小花费

	int minCostPlanIndex = -1;    // 最小花费对应的攻略编号（从 1 开始）

	for (int planIndex = 1; planIndex <= k; ++planIndex) {

		int pathLength;

		cin >> pathLength;

		vector<int> path(pathLength + 1); // 路径，path[0] 为从家出发

		path[0] = 0;

		for (int i = 1; i <= pathLength; ++i) {

			cin >> path[i];

		}

		// 记录访问情况，判断是否每个网红点访问一次

		vector<bool> visited(n + 1, false);

		int uniquePoints = 0;

		int totalCost = 0;

		bool isValid = true;

		// 从家出发到第一个网红点的花费

		if (cost[0][path[1]] == inf) {

			isValid = false;

		} else {

			totalCost += cost[0][path[1]];

		}

		for (int i = 1; i < pathLength && isValid; ++i) {

			int curr = path[i];

			int next = path[i + 1];

			// 点编号合法性

			if (curr < 1 || curr > n || next < 1 || next > n) {

				isValid = false;

				break;

			}

			// 重复访问检查

			if (visited[curr]) {

				isValid = false;

				break;

			}

			visited[curr] = true;

			uniquePoints++;

			// 路径连通性检查

			if (cost[curr][next] == inf) {

				isValid = false;

				break;

			}

			totalCost += cost[curr][next];

		}

		// 最后一个点是否已访问，回家是否可达

		int lastPoint = path[pathLength];

		if (!visited[lastPoint]) uniquePoints++;

		if (visited[lastPoint] || cost[lastPoint][0] == inf || uniquePoints != n) {

			isValid = false;

		} else {

			totalCost += cost[lastPoint][0]; // 回家

		}

		if (isValid) {

			validPlanCount++;

			if (totalCost < minCost) {

				minCost = totalCost;

				minCostPlanIndex = planIndex;

			}

		}

	}

	cout << validPlanCount << endl;

	cout << minCostPlanIndex << " " << minCost << endl;

	return 0;

}

同类题型

视频讲解

⬅️ L2-035 完全二叉树的层序遍历 🏠 00-天梯赛 ➡️ L2-037 包装机