求助 #3死循环

#include<iostream>
#include<cstdio>

#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
struct line
{
    int to,ne;
}st[1500];
long long a[1501],dp[1501][3];
int n,p,no,h[1501],s[1501],f[1501],vis[1501],ss[1501];
void add(int x,int y)
{
    st[++p].to=y;
    st[p].ne=h[x];
    h[x]=p;
}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&no);
        scanf("%lld%d",&a[no],&s[no]);
        ss[no]=s[no];
        for(int j=1;j<=s[no];j++)
        {
            int x;
            scanf("%d",&x);
            add(no,x);
            f[x]=no;
        }
    }
    for(int j=1;j<=n;j++)
    {
        if(!ss[j]&&!vis[j])
        {
            dp[j][1]=a[j];
            dp[j][0]=1e15+10;
            dp[j][2]=0;
            ss[f[j]]--;
            vis[f[j]]=1;
            ss[j]--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n;j++)
        {
            if(ss[j]==0&&vis[j]==0)
            {
                
                int yes=1;
                if(h[j]!=0)
                yes=0;
                for(int ii=h[j];ii;ii=st[ii].ne)
                {
                    if(dp[st[ii].to][1]<=dp[st[ii].to][0])
                    yes=1;
                    dp[j][2]+=min(dp[st[ii].to][0],dp[st[ii].to][1]);
                    dp[j][1]+=min(dp[st[ii].to][0],min(dp[st[ii].to][1],dp[st[ii].to][2]));
                }
                dp[j][1]+=a[j];
                dp[j][0]=dp[j][2];
                if(f[j]==0)
                dp[j][2]=1e15+10;
                if(!yes)
                {
                    long long mi=1e15+10;
                    for(int ii=h[j];ii;ii=st[ii].ne)
                    {
                        mi=min(mi,dp[st[ii].to][1]-dp[st[ii].to][0]);
                    }
                    dp[j][0]+=mi;
                }
                ss[f[j]]--;
                vis[f[j]]=1;
                ss[j]--;
                if(f[j]==0)
                {
                    printf("%lld",min(dp[j][0],min(dp[j][1],dp[j][2])));
                    return 0;
                }
            }
        }
    }
    return 0;
}

1 条评论

  • 1

信息

ID
1144
难度
7
分类
动态规划 | 树形DP 点击显示
标签
递交数
4561
已通过
1001
通过率
22%
被复制
10
上传者