比赛 |
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);
}