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"; }