L2-036 网红点打卡攻略 (25 分) Java题解 （图，模拟）

输入样例：

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 条花费相同，但序号较大，所以不输出。

解题思路：

题意大致是给出若干个序列，判断合法序列数，合法条件为序列中的点在图中正好都只出现过一次，并且相邻两点都有通路。从0号点开始，遍历完景点，再回到0号点，输出合法条数和最小权值即可。

Java代码：

import java.io.*;
import java.util.Arrays;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int m = Integer.parseInt(split[1]);
		
		final int INF = 0x3f3f3f3f;
		int [][]g = new int[n + 1][n + 1];
		boolean []vis = new boolean[n + 1]; // 标志是否访问过该点
		for(int i = 0; i <= n; i++) Arrays.fill(g[i], INF);
		
		while(m-- > 0) {
			split = br.readLine().split(" ");
			int a = Integer.parseInt(split[0]);
			int b = Integer.parseInt(split[1]);
			int w = Integer.parseInt(split[2]);
			g[a][b] = g[b][a] = w;
		}
		
		int k = Integer.parseInt(br.readLine());
		int idx = -1, ans = Integer.MAX_VALUE, count = 0;
		for(int j = 1; j <= k; j++) {
			int cnt = n;  // 记录共访问了几个点
			vis = new boolean[n + 1];
			split = br.readLine().split(" ");
			m = Integer.parseInt(split[0]);
			int []arr = new int[m];
			for(int i = 0; i < m; i++)
				arr[i] = Integer.parseInt(split[i + 1]);
			
			int sum = 0;  // 从家到第一个点
			if(g[0][arr[0]] != INF) sum += g[0][arr[0]];
			else continue;
			
			int i = 0;
			for(i = 0; i < m - 1; i++)  // 遍历所有景点
				if(g[arr[i]][arr[i + 1]] != INF && !vis[arr[i]]) {
					sum += g[arr[i]][arr[i + 1]];
					vis[arr[i]] = true;
					cnt--;
				}else break;
			if(i != m - 1) continue;
			
			if(g[arr[m - 1]][0] != INF && !vis[arr[m - 1]]) { // 从最后一个景点回到家
				 sum += g[arr[m - 1]][0];
				 vis[arr[m - 1]] = true;
				 cnt--;
			}else continue;
			
			if(cnt != 0) continue;  // 如果访问的不是正好n个点，则不符合题意
			
			count++; // 满足要求的方案数
			if(ans > sum) {
				ans = sum;
				idx = j;
			}
		}
		
		System.out.println(count);
		System.out.println(idx + " " + ans);
	}
}