- 小胖守皇宫
- 2019-11-26 16:30:55 @
#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 条评论
-
gary88 LV 7 @ 2019-11-28 16:10:06
已解决
- 1