记录编号	358894	评测结果	AAAAAAAAAA
题目名称	[USACO Jan15] 牛的路线2	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2016-12-19 16:36:28	内存使用	0.64 MiB

//KZNS
#include <cstdio>
#include <algorithm>
using namespace std;
#define Pmax 10003

int F[Pmax][4];
int G[Pmax][4];
int ls[Pmax];
int main() {
	freopen("cowrouteb.in", "r", stdin);
	freopen("cowrouteb.out", "w", stdout);
	int A, B, N, M;
	scanf("%d %d %d", &A, &B, &N);
	int ans = 0x7fffffff;
	int P;
	int S, T;
	int t;
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &P, &M);
		S = T = -1;
		for (int j = 0; j < M; j++) {
			scanf("%d", &ls[j]);
			if (ls[j] == A)
				S = j;
			if (ls[j] == B)
				T = j;
		}
		if (S >= 0 && T >= 0 && S < T) {
			ans = min(ans, P);
			continue;
		}
		if (S >= 0) {
			for (int j = S+1; j < M; j++) {
				t = ls[j];
				if (F[t][1] == 0 || F[t][0] > P) {
					F[t][2] = F[t][0];
					F[t][3] = F[t][1];
					F[t][0] = P;
					F[t][1] = i;
				}
				else if (F[t][3] == 0 || F[t][2] > P) {
					F[t][2] = P;
					F[t][3] = i;
				}
			}
		}
		if (T >= 0) {
			for (int j = 0; j < T; j++) {
				t = ls[j];
				if (G[t][1] == 0 || G[t][0] > P) {
					G[t][2] = G[t][0];
					G[t][3] = G[t][1];
					G[t][0] = P;
					G[t][1] = i;
				}
				else if (G[t][3] == 0 || G[t][2] > P) {
					G[t][2] = P;
					G[t][3] = i;
				}
			}
		}
	}
	for (int i = 1; i <= 10000; i++) {
		if (i == A || i == B)
			continue;
		if (F[i][1] && G[i][1]) {
			if (F[i][1] == G[i][1]) {
				if (F[i][3])
					ans = min(ans, F[i][2] + G[i][0]);
				if (G[i][3])
					ans = min(ans, F[i][0] + G[i][2]);
			}
			else
				ans = min(ans, F[i][0] + G[i][0]);
		}
	}
	if (ans == 0x7fffffff)
		printf("-1\n");
	else
		printf("%d\n", ans);
	return 0;
}
//UBWH