题目解析
给定M条路，以及K中旅游攻略。
问一共有多少个满足条件的旅游攻略，以及最少花费的旅游攻略编号以及花费。
解题思路
按照题意模拟即可
可以用数组去判断当前旅游攻略中，每个打卡点是否走过。
- 在判断攻略中，每个点是否都能到达下一个点
- 以及是否能从家出发到第一个打卡点
- 以及最后一个点是否能到达家
如果都可以，则去找最小的即可
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int inf = 0x3f3f3f3f;
public static void main(String[] args) throws IOException
{
int N = ini();
int M = ini();
int map[][] = new int[N + 10][N + 10]; // 存储i到j的最短路
for (int i = 0; i <= N; i++) Arrays.fill(map[i], inf);
while (M-- > 0)
{
int a = ini();
int b = ini();
int c = ini();
map[a][b] = map[b][a] = Math.min(map[a][b], c); // 更新i到j的最短路
}
int shu[] = new int[N + 10]; // 存储路径
boolean vis[] = new boolean[N + 10]; // 判断当前这个地方是否打卡过
int min = inf; // 存储最少花费
int cnt = 0; // 存储满足要求的攻略个数
int pos = 0; // 存储最少花费的第一个路径
int k = ini();
for (int T = 1; T <= k; T++)
{
Arrays.fill(vis, false);
boolean f = false; // 判断当前点是否打卡过
int n = ini();
for (int i = 1; i <= n; i++)
{
shu[i] = ini();
if (vis[shu[i]]) f = true; // 当前点打卡过
vis[shu[i]] = true;
}
// 如果当前点打卡过 或者 是否全部游玩过 或者 可以从家到第一个打卡点 或者 可以从最后一个打卡点到家
if (f || n != N || map[0][shu[1]] == inf || map[shu[n]][0] == inf) continue;
int ans = map[0][shu[1]] + map[shu[n]][0]; // 计算总花费
for (int i = 2; i <= n; i++)
{
int x = map[shu[i - 1]][shu[i]];
if (x == inf) // 如果当前点无法打卡
{
ans = inf; // 将当前总花费舍弃
break;
}
ans += x;
}
if (ans >= inf) continue; // 当前花费为舍弃的
cnt++; // 次数增加
if (min > ans) // 如果出现了更少的花费
{
min = ans;
pos = T;
}
}
out.println(cnt);
out.println(pos + " " + min);
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
}