L2-036 网红点打卡攻略
Statement
Metadata
- 作者: 陈越
- 单位: 浙江大学
- 代码长度限制: 16 KB
- 时间限制: 400 ms
- 内存限制: 64 MB
一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
输入格式
首先第一行给出两个正整数:网红点的个数 0
。
再下一行给出一个正整数
其中
输出格式
在第一行输出满足要求的攻略的个数。
在第二行中,首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号(从 1 开始),然后输出这个攻略的总路费,其间以一个空格分隔。如果这样的攻略不唯一,则输出序号最小的那个。
题目保证至少存在一个有效攻略,并且总路费不超过
输入样例
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
输出样例
样例说明
第 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 条花费相同,但序号较大,所以不输出。
Solution
#include <bits/stdc++.h>
using namespace std;
using db = long double;
using ll = long long;
using pII = pair<int, int>;
#define fi first
#define se second
const int N = 2e2 + 10;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, m, q, g[N][N];
ll get(vector<int> vec) {
vec.push_back(0);
int st = 0;
ll res = 0;
vector<int> vis(n + 1, 0);
for (auto &it : vec) {
if (g[st][it] == INF)
return INFLL;
res += g[st][it];
st = it;
vis[it]++;
}
for (int i = 1; i <= n; ++i) {
if (vis[i] != 1)
return INFLL;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1, u, v, w; i <= m; ++i) {
cin >> u >> v >> w;
g[u][v] = w;
g[v][u] = w;
}
int num = 0, ix = -1;
ll Min = INFLL;
cin >> q;
for (int i = 1; i <= q; ++i) {
int _n;
cin >> _n;
vector<int> vec(_n);
for (auto &it : vec) cin >> it;
ll cost = get(vec);
if (cost < Min) {
Min = cost;
ix = i;
}
if (cost < INFLL) {
++num;
}
}
cout << num << endl;
cout << ix << ' ' << Min << endl;
return 0;
}