-12/cy

BFS应该如何优化/kel

最后试过优先队列，但是一直 TLE ON 6

/*
+   +   +   +    +++     +++++     ++++
 + +     + +      +         +      +   +
  +       +       +        +       +   +
 + +      +       +       +        +   +
+   +     +      +++     +++++     ++++
*/
#include<bits/stdc++.h>
//#define int ll
#define pb push_back
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int N=1000005;
const int inf=1<<30;
const ll inff=1ll<<60;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,v[15][100005],c[100005],m,cnt,b[100005][15];
ll ans,res;
struct CatherineAns{
	int a[15]; ll s;
}p,out,pp;
queue<CatherineAns>q;
bool check(CatherineAns x,int t){
	for(int i=1;i<=n;i++)
	if(x.a[i]!=b[t][i])return 0;
	return 1;
}
void sp(CatherineAns x){
	for(int i=1;i<=n;i++)p.a[i] = x.a[i];
	p.s = x.s;
	for(int i=1;i<=n;i++)
		if(p.a[i]>1){
			p.a[i]--;
			p.s -= v[i][p.a[i]+1]-v[i][p.a[i]];
			if(p.s>ans)
			q.push(p);
			p.s +=v[i][p.a[i]+1]-v[i][p.a[i]];
			p.a[i]++;
			
	    }
}
int main(){int tests=1;//tests=read();
while(tests--){
	n=read();
	for(int i=1;i<=n;i++){
		c[i]=read();
		for(int j=1;j<=c[i];j++)v[i][j]=read();
	}
	m=read();
	for(int i=1;i<=m;i++)
	    for(int j=1;j<=n;j++)b[i][j]=read();
	pp.s=0;
	for(int i=1;i<=n;i++)pp.a[i]=c[i] , pp.s += v[i][c[i]];
	q.push(pp);
	while(!q.empty()){
		bool ok=1;
		pp = q.front(),q.pop();
		if(pp.s<=ans)continue;
		//printf("%lld\n",pp.s);
		for(int j=1;j<=m;j++)
		if(check(pp,j)){
			ok = 0 ; break;
		}
		if(ok){
		    ans = pp.s, out = pp; 
		}
		else{
			sp(pp);
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",out.a[i]);
}	return 0;
}