If Bessie travels for exactly $t$ days then the amount of moonies that she makes is bounded above by $1000t-t^2,$ which is negative when $t>1000.$ Thus, it suffices to keep track of the DP states $dp[x][t]$ for each $1\le x\le N, 0\le t\le 1000,$ denoting the maximum amount of moonies Bessie can make up to time $t$ if she is located at city $x$ at time $t$. The final answer will be $\max_{0\le t\le 1000}(dp[1][t]-Ct^2).$ This solution runs in $O(\max(m_i)\cdot (N+M)).$ time.

Mark Chen's code:

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1005;
const int MAXT = 1005;
 
long long n, m, c;
long long value[MAXN];
long long dp[2][MAXN];
 
vector<pair<int, int>> edges;
 
int main() {
	freopen("time.in","r",stdin);
	freopen("time.out","w",stdout);
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++) {
		cin >> value[i];
	}
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		edges.push_back(make_pair(a, b));
	}
	long long max_profit = 0;
	memset(dp, -1, sizeof dp);
	dp[0][1] = 0;
	for (int t = 1; t < MAXT; t++) {
		int p = t % 2;
		memset(dp[p], -1, sizeof dp[p]);
		for (auto& e : edges) {
			a = e.first;
			b = e.second;
			if (dp[1-p][a] >= 0) {
				dp[p][b] = max(dp[p][b], dp[1-p][a] + value[b]);
			}
		}
		max_profit = max(max_profit, dp[p][1] - c * t * t);
	}
	cout << max_profit << "\n";
}