显示代码纯文本
#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);
}