比赛 20161215 评测结果 AAAWAATTTT
题目名称 牛的路线2 最终得分 50
用户昵称 confoo 运行时间 4.353 s
代码语言 C++ 内存使用 39.28 MiB
提交时间 2016-12-16 21:49:17
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define file(x) "cowrouteb." #x
const int V = 510, C = 10000 + 10, INF = 0x3f3f3f3f;
using std::min;
int n, s, t, w[V], ans = INF, inl[C], st[C][V], tt[C][V];
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d%d%d", &s, &t, &n);
	memset(st, 0x3f, sizeof(st));
	memset(tt, 0x3f, sizeof(tt));
	for (int i = 1; i <= n; i++) {
		memset(inl, 0, sizeof(inl));
		int c;
		scanf("%d%d", &w[i], &c);
		for (int j = 1; j <= c; j++){
			int x;
			scanf("%d", &x);
			inl[x] = j;
		}
		for (int x = 1; x < C; x++) {
			if (inl[s] && inl[x] && inl[s] <= inl[x]) st[x][i] = w[i];
			if (inl[x] && inl[t] && inl[x] <= inl[t]) tt[x][i] = w[i];
		}
		if (inl[s] && inl[t] && inl[s] <= inl[t]) ans = min(ans, w[i]);
	}
	for (int i = 1; i < C; i++) 
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++) if (k != j)
			ans = min(ans, st[i][j] + tt[i][k]);
	printf("%d", ans);
}