rt。随便写的垃圾代码也能过,不是凡尔赛,真的是题目数据太水导致大家都被动凡尔赛。不够蓝题难度,可降。
#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <string>
#include <bitset>
#include <stack>
#include <random>
#include <functional>
using namespace std;
typedef unsigned long long ull;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
constexpr ll MAXN = 3e5 + 10;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1ll << 62;
#define mkp make_pair
#define stop 1 == 1;
#define lt root << 1
#define rt root << 1 | 1
template<typename T> void read_single(T& x){
x = 0;
char g = getchar();
bool f = true;
while(!isdigit(g)){if(g == '-')f = !f;g = getchar();}
while(isdigit(g)){x = (x << 1) + (x << 3) + (g ^ 48);g = getchar();}
x = f ? x : -x;
}
void read(){}
template<typename T, typename... Args>
void read(T& x, Args&... args) {
read_single(x);
read(args...);
}
template<typename T> void write(T x){
if(x < 0){putchar('-');x = -x;}
if(x > 9)write(x / 10);
putchar(x % 10 ^ 48);
}
struct Edge{
ll idx, w;
vector<ll> adj[2];
unordered_map<ll, int> toSide;
};
void dfs(vector<Edge>& e,
ll& sum, ll Idx, int Trn,
vector<bool>& vis, ll& ans,
ll fa, ll u){
auto&c = e[u];
sum += c.w;
vis[u] = true;
int trn = c.toSide[fa] ^ 1;
auto finish = c.adj[trn].end();
auto iter = lower_bound(c.adj[trn].begin(), finish, Idx);
for(;iter != finish; iter++){
auto v = *iter;
if(v == Idx && e[v].toSide[u] == Trn){
ans = min(ans, sum);
}
if(vis[v])continue;
dfs(e, sum, Idx, Trn, vis, ans, u, v);
}
sum -= c.w;
vis[u] = false;
};
void solve(){
ll N; read(N);
vector<ll> changeIdx(N + 1);
for(ll i = 0; i <= N; i++)changeIdx[i] = i;
random_device rd;
mt19937 G(rd());
shuffle(changeIdx.begin() + 1, changeIdx.end(), G);
vector<Edge> e(N + 1);
ll n[2];
for(int k = 1; k <= N; k++){
auto& c = e[k];
read(c.idx, c.w, n[0], n[1]);
c.idx = changeIdx[c.idx];
for(int i = 0; i < 2; i++){
while(n[i]--){
ll jdx; read(jdx);
jdx = changeIdx[jdx];
c.adj[i].emplace_back(jdx);
c.toSide[jdx] = i;
}
sort(c.adj[i].begin(), c.adj[i].end());
}
}
sort(e.begin() + 1, e.end(), [&](const Edge& a, const Edge& b){
return a.idx < b.idx;
});
ll ans = INF;
for(int k = 1; k <= N; k++){
auto& c = e[k];
ll u = c.idx;
if(c.adj[0].back() < c.idx || c.adj[1].back() < c.idx)continue; // 剪枝
ll sum = c.w;
vector<bool> vis(101, false);
vis[u] = true;
auto finish = c.adj[0].end();
auto iter = lower_bound(c.adj[0].begin(), finish, c.idx);
for(;iter != finish; iter++){
auto v = *iter;
dfs(e, sum, u, 1, vis, ans, u, v);
}
}
write(ans);
cout << flush;
return;
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
ll T = 1;
// read(T);
while(T--){
solve();
}
return 0;
}
/*
10
1 16 2 2
2 7
10 6
2 3 2 2
1 7
8 3
3 3 2 1
8 2
4
4 8 1 3
3
9 10 5
5 8 3 1
9 10 4
6
6 6 1 2
5
1 10
7 5 2 2
1 2
8 9
8 4 2 2
2 3
7 9
9 5 2 3
7 8
4 5 10
10 10 2 3
1 6
4 9 5
*/