PTA 网红点打卡攻略

本文主要是介绍PTA 网红点打卡攻略，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
在这里插入图片描述
输入样例

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出样例

3
5 11

样例说明

第 2、3、4、6 条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有 3 条。

第 1 条攻略的总路费是：(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14；

第 5 条攻略的总路费同理可算得：1 + 1 + 1 + 2 + 3 + 1 + 2 = 11，是一条更省钱的攻略；

第 7 条攻略的总路费同理可算得：2 + 1 + 1 + 2 + 2 + 2 + 1 = 11，与第 5 条花费相同，但序号较大，所以不输出。

$F l o y e d$ 算法求最短路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 207;
typedef long long ll;
ll mp[maxn][maxn];
ll a[maxn];
int vis[maxn][maxn];
int num[maxn];
int main()
{int n,m;scanf(" %d %d",&n,&m);//init()for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)mp[i][j] = 1e18, vis[i][j] = 0;for(int i = 1; i <= m; i++){int x,y; ll dis;scanf(" %d %d %lld",&x,&y,&dis);mp[x][y] = dis; mp[y][x] = dis;vis[x][y] = 1; vis[y][x] = 1;}//floyed()for(int k = 0; k <= n; k++)for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)if(mp[i][j] >= mp[i][k] + mp[k][j] && vis[i][j] && vis[i][k] && vis[k][j])mp[i][j] = mp[i][k] + mp[k][j];int t;scanf("%d",&t);ll ans = 1e18;int cnt = 0, pos = 0;for(int i = 1; i <= t; i++){int tot, s = 0, e;scanf(" %d",&tot);int ok = 0;ll sum = 0;memset(num,0,sizeof num);for(int j = 1; j <= tot; j++){scanf("%d",&e);num[s]++; num[e]++;if(vis[s][e]) sum += mp[s][e];else if(vis[e][s]) sum += mp[e][s];else ok = 1;s = e;}num[0]++, num[e]++;for(int i = 0; i <= n; i++)if(num[i] != 2) ok = 1;if(ok) continue;else{if(vis[e][0] || vis[0][e]){if(vis[0][e]) sum += mp[0][e];else if(vis[e][0]) sum += mp[e][0];cnt++;if(ans > sum) ans = sum, pos = i;}}}printf("%d\n",cnt);printf("%d %lld\n",pos, ans);return 0;
}