---

L2-036 网红点打卡攻略 ( 模拟题 )

原创 于 2024-04-03 13:05:43 发布 · 粉丝可见 · 363 阅读 · 10 · 3 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137341324

本题链接： PTA | 程序设计类实验辅助教学平台

题目：

样例：

cobol<br/>6 13<br/>0 5 2<br/>6 2 2<br/>6 0 1<br/>3 4 2<br/>1 5 2<br/>2 5 1<br/>3 1 1<br/>4 1 2<br/>1 6 1<br/>6 3 2<br/>1 2 1<br/>4 5 3<br/>2 0 2<br/>7<br/>6 5 1 4 3 6 2<br/>6 5 2 1 6 3 4<br/>8 6 2 1 6 3 4 5 2<br/>3 2 1 5<br/>6 6 1 3 4 5 2<br/>7 6 2 1 3 4 5 2<br/>6 5 2 1 4 3 6<br/>

3 5 11

思路：

根据题目意思模拟一遍就可以了。

根据数据范围N <= 200,所以我们可以弄一个邻接矩阵，然后就方便很多了。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f3f3f
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
int n,m,rid,ans = INF,ansSumPath;
int g[500][500];	// 邻接图
inline void InPutInfo()
{
	// 各点间距离无穷大，表示还未相连
	memset(g,INF,sizeof g);
	
	cin >> n >> m;
	while(m--)
	{
		int a,b,c;
		cin >> a >> b >> c;
		
		g[a][b] = min(g[a][b],c);	//相连两点，取少花费
		swap(a,b);
		g[a][b] = min(g[a][b],c);	//相连两点，取少花费
	}
}
 
inline void InPutPlan()
{
	// 输入总攻略
	cin >> m;
	for(int id = 1;id <= m;++id)
	{
		int sz;
		cin >> sz;
		bool vis = false;	// vis 用于判断是否有重复打卡地点
		vector<bool>st(210,false);	// st 用于标记是否已经走过
		vector<int>plan;// 输入打卡点
		for(int i = 0,x;i < sz;++i)
		{
			cin >> x;
			if(st[x]) vis = true;
			st[x] = true;
			plan.emplace_back(x);
		}
		// 如果存在 重复打卡的地点  或者 存在不能回到家的攻略 或者 没有走完全部地点 则该攻略不符合要求
		if(vis || g[*plan.begin()][0] >= INF || g[plan.back()][0] >= INF || sz != n) continue;
		
		int now = *plan.begin();	// now 表示当前走到的网红打卡点
		int w = g[*plan.begin()][0];	// w 表示总花费 这里是出门到达第一个打卡点的花费
		
		for(int i = 1;i < sz;++i)
		{
			// 如果出现攻略有无法到达下一个地点的情况，则攻略不符合要求
			if(g[now][plan[i]] >= INF) goto here;	
			
			w += g[now][plan[i]];	// 累计总花费
			now = plan[i];	// 更新到达的地点
		}
		
		w += g[now][0];	// 累计最后重新回到家的花费
		
		
		++ansSumPath;	// 累计符合要求的攻略数量
		if(ans > w)	// 如果出现更少的花费
		{
			ans = w;	// 更新最少花费
			rid = id;	// 记录最好花费最小的序号
		}
		here:;
	}
}
 
inline void PrintAns()
{
	cout << ansSumPath << endl;
	cout << rid << ' ' << ans << endl;
}
 
inline void solve()
{
	// 输入地点信息
	InPutInfo();
	
	// 输入攻略
	InPutPlan();
	
	// 输出答案
	PrintAns();
}

最后提交：