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

#include <cstdio>
#include <cstring>
#include <algorithm>
#define file(x) "cowrouteb." #x
using std::min;
const int V = 1e5 + 10, N = 510, INF = 0x3f3f3f3f;
int s, t, n, st[V][2], tt[V][2], w[N], pos[V], ans = INF;
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d%d%d", &s, &t, &n);
	memset(w, 0x3f, sizeof(w));
	for (int i = 1; i <= n; i++) {
		memset(pos, 0, sizeof(pos));
		int c;
		scanf("%d%d", &w[i], &c);
		for (int j = 1; j <= c; j++) {
			int x;
			scanf("%d", &x);
			pos[x] = j;
		}
		if (pos[s]) for (int j = 1; j < V; j++) if (pos[j] && pos[s] < pos[j]) {
			if (w[i] < w[st[j][0]]) st[j][1] = st[j][0], st[j][0] = i;
			else if (w[i] < w[st[j][1]]) st[j][1] = i;
		}
		if (pos[t]) for (int j = 1; j < V; j++) if (pos[j] && pos[j] < pos[t]) {
			if (w[i] < w[tt[j][0]]) tt[j][1] = tt[j][0], tt[j][0] = i;
			else if (w[i] < w[tt[j][1]]) tt[j][1] = i;
		}	
		if (pos[s] && pos[t] && pos[s] < pos[t]) ans = min(ans, w[i]);
	}
	for (int i = 1; i < V; i++) 
		for (int k = 0; k < 2; k++) {
			int x = st[i][k], y = tt[i][0] == x ? tt[i][1] : tt[i][0];
			ans = min(ans, w[x] + w[y]);
		}
	printf("%d", ans == INF ? -1 : ans);
}