看到没人写题解，我就来写一篇

前言

考场上看到这道题我是崩溃的，感觉没有思路

后来仔细分析了一下这道题的数据范围，好像不大

于是我暴力+一些优化过了

解法

考虑bfs

bfs的方法我就不说了，比较简单；我们来说说我加的两个优化

优化1：搜索时间限制

这里有一个看似没用的简单结论：

当我之后走的每一步都会亏本，我就不走了

正确性自然不用证明，但是这个结论有啥用呢？

我们设 $T$ 为走的总时间，$maxval$ 为所有的城市中得钱最多的

于是我们可以得到这样的一个不等式：

什么意思呢？就是假设每次走都可以得到 $maxval$ 块钱，走这些路程能赚的钱数

解得：

这样，我们就可以限制bfs时搜索的时间，也就是一个搜索边界

优化2：最优性剪枝

原理：当我们在 $t_1$ 时刻走到一个点，而在此之前，存在一个 $t_2\le t_1$ 时刻在当前点的得钱比现在多，那么当前的搜索是没有意义的，结束当前分枝的搜索

应该比较好理解吧

代码

#include<bits/stdc++.h>
#define MAXN 2010
using namespace std;
int n,m,c;
int val[MAXN];
struct Node
{
	int to,next;
}Edge[MAXN<<1];
int Head[MAXN],cnt_Edge;
void Add_Edge(int u,int v)
{
	Edge[++cnt_Edge].to=v;
	Edge[cnt_Edge].next=Head[u];
	Head[u]=cnt_Edge;
}//链表存图
int T,ans;
int ear[MAXN][MAXN];//这里是earn的缩写，不是耳朵qwq，用于最优性剪枝
struct Nodex
{
	int now,tim,dis;
};
void bfs()
{
	queue<Nodex>Q;
	Q.push((Nodex){1,0,0});//队列中存当前节点，到达当前节点的时间，到达当前节点赚的钱
	while(!Q.empty())
	{
		Nodex tmp=Q.front();Q.pop();
		int u=tmp.now,t=tmp.tim,w=tmp.dis;
		for(int i=Head[u];i;i=Edge[i].next)
		{
			int v=Edge[i].to,nowt=t+1,noww=w+val[v];
			if(v==1)ans=max(ans,w-c*nowt*nowt);//统计答案
			bool fl=true;
			for(int j=nowt;j>=1;j--)
				if(ear[v][j]>=noww-c*nowt*nowt)
				{
					fl=false;
					break;
				}//最优性剪枝
			if(!fl)continue;
			ear[v][nowt]=noww-c*nowt*nowt;
			if(nowt<T)Q.push((Nodex){v,nowt,noww});//搜索边界
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&c);
	int val_max=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&val[i]);
		val_max=max(val_max,val[i]);
	}
	T=val_max/c;//搜索边界
	for(int i=1;i<=m;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		Add_Edge(u,v);
	}
	bfs();
	printf("%d",ans);
	return 0;
}