思路:想到用图论前驱图了,但是因为考虑可能有环的存在,但是其实题干中说明了不能通过一种或几种混合得到自己,所以就保证了不存在环,那就能用拓扑结构的性质做,用记忆化搜索就可以了
- // Problem: E. Nastya and Potions
- // Contest: Codeforces - Codeforces Round 888 (Div. 3)
- // URL: https://codeforces.com/contest/1851/problem/E
- // Memory Limit: 256 MB
- // Time Limit: 3000 ms
-
- #include
- #include
- #include
- #define fi first
- #define se second
- #define i128 __int128
- using namespace std;
- typedef long long ll;
- typedef double db;
- typedef pair<int,int> PII;
- const double eps=1e-7;
- const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
- const long long int llINF=0x3f3f3f3f3f3f3f3f;
- inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
- while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
- inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
- inline void write(ll x,char ch) {write(x);putchar(ch);}
- void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
- bool cmp0(int a,int b) {return a>b;}
- template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
- template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
- void hack() {printf("\n----------------------------------\n");}
-
- int T,hackT;
- int n,m,k;
- ll cost[N];
- bool st[N];
- int h[N],e[M],ne[M],w[M],idx;
-
- void add(int a,int b) {
- e[idx]=b,ne[idx]=h[a],h[a]=idx++;
- }
-
- void dfs(int u) {
- if(h[u]==-1) {
- st[u]=true;
- return ;
- }
-
- ll res=0;
- for(int i=h[u];i!=-1;i=ne[i]) {
- int j=e[i];
- if(!st[j]) dfs(j);
- res+=cost[j];
- }
-
- st[u]=true;
- cost[u]=min(res,cost[u]);
- }
-
- void solve() {
- n=read(),k=read();
-
- for(int i=1;i<=n;i++) cost[i]=read(),st[i]=false;
- for(int i=1;i<=k;i++) {
- int c=read();
- cost[c]=0;
- st[c]=true;
- }
-
- memset(h,-1,sizeof(int)*(n+4));
- idx=0;
- for(int i=1;i<=n;i++) {
- int m=read();
- for(int j=1;j<=m;j++) {
- int c=read();
- add(i,c);
- }
- }
-
- for(int i=1;i<=n;i++) {
- if(!st[i]) dfs(i);
- printf("%d ",cost[i]);
- }
-
- printf("\n");
- }
-
- int main() {
- // init();
- // stin();
- // ios::sync_with_stdio(false);
-
- scanf("%d",&T);
- // T=1;
- while(T--) hackT++,solve();
-
- return 0;
- }