P6005 [USACO20JAN]Time is Mooney G

[USACO20JAN]Time is Mooney G - 洛谷

算法标签：SPFA+枚举

难度：普及+/提高

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 1010
#define P pair 
int n,m,C,a[N],cnt,h[N],v[N][N],dp[N][N],ans;
struct Node
{
	int nxt,to,val;
}e[2*N];
queue < P > q;

void AddEdge (int x,int y)
{
	e[++cnt].nxt=h[x];h[x]=cnt;
	e[cnt].to=y;
}

void Init ()
{
	cin>>n>>m>>C;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		AddEdge (x,y);
	}
}

void BFS ()
{
	q.push (make_pair (1,0));
	v[1][0]=1;
	while (!q.empty ())
	{
		int x=q.front ().first;
		int t=q.front ().second;
		q.pop ();
		v[x][t]=0;
		if (t>=1000) continue;
		for (int i=h[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if (dp[x][t]+a[y]>dp[y][t+1])
			{
				dp[y][t+1]=dp[x][t]+a[y];
				if (!v[y][t+1])
				{
					q.push (make_pair (y,t+1));
					v[y][t+1]=1; 
				}
			}
		}
	}
}

void Work ()
{
	BFS ();
	for (int i=0;i<=1000;i++)
		ans=max (ans,dp[1][i]-C*i*i);
	cout<