求助，萌新不会dp，t了9个点。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
const int maxm=2005;
struct Edge{
    int v,nxt;
}e[maxm];
int n,m,c,cnt,ans;
int mooney[maxn],head[maxn];
int f[maxn][maxn]; //f[i][j]表示第i天到第j城市mooney最大值
void addEdge(int u,int v){
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}
int main()
{
    memset(f,-1,sizeof f);
    f[0][1]=0;
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=n;i++){
        scanf("%d",&mooney[i]);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(y,x);
    }
    for(int i=1;i<=maxn;i++){
        for(int j=1;j<=n;j++){
            for(int k=head[j];k;k=e[i].nxt){
                int v=e[k].v;
                if(f[i-1][v]!=-1) f[i][j]=max(f[i][j],f[i-1][v]+mooney[v]);
            }
        }
        ans=max(ans,f[i][1]-c*i*i);
    }
    printf("%d",ans);
    
    

    return 0;
}