为什么RE*9+WA*1
查看原帖
为什么RE*9+WA*1
173239
黄汝鹏楼主2019/9/7 10:37
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iomanip>
#include<queue>
#include<algorithm>
#include<bits/stdc++.h>
#define edge(u)for(int i=head[u],to=go[i];i;i=next[i],to=go[i])
#define egde(u)for(int i=head2[u],to=go2[i];i;i=next2[i],to=go2[i])
using namespace std;
const int N=200000+10,M=1e6+10,L=15e6+10;
int n,r[N],num,num2,x,q[L],head[N],head2[N];
long long f[N],s[N],k[N];
int go[M],go2[M],next[M],next2[M];
bool v[N];
inline int read()
{
	int res=0;bool bo=0;char c;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-') bo=1;
	else res=c-48;
	while((c=getchar())>='0'&&c<='9')
	      res=(res<<30)+(res<<1)+(c-48);
	return bo? ~res+1:res;
}
inline long long readlong()
{
	long long res=0;bool bo=0;char c;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-') bo=1;
	else res=c-48;
	while((c=getchar())>='0'&&c<='9')
	      res=(res<<30)+(res<<1)+(c-48);
	return bo? ~res+1:res;
}
void add_edge(int from,int to)
{
	num++;
	next[num]=head[from];
	head[from]=num;
	go[num]=to;
}
void add_edge2(int from,int to)
{
	num2++;
	next2[num2]=head2[from];
	head2[from]=num2;
	go2[num2]=to;
}
long long spfa()
{
	int h=0,t=n;
	for(int i=1;i<=n;i++) q[i]=i,f[i]=k[i],v[i]=1;
    while(h<t)
	{
		int u=q[++h];
		v[u]=0;
		long long ans=s[u];
		edge(u) ans+=f[to];
		if(ans>=f[u]) continue;
		f[u]=ans;
		egde(u) if(!v[to]) v[to]=1,q[++t]=to;
	}
	return f[1];	
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		s[i]=readlong(),k[i]=readlong(),r[i]=read();
		for(int j=1;j<=r[i];j++) x=read(),add_edge(i,x),add_edge2(x,i);
	}
	cout<<spfa()<<endl;
	return 0;
} 
2019/9/7 10:37
加载中...