ポテンシャル，ダイクストラ．
まず，登りが下りのコストの \(-1\) 倍の場合を考える． これは簡単で，始点と終点のみで決まる．
次に，登りが下りのコストの \(-2\) 倍の場合を考える． この場合，\(s\)から\(t\)へのコストは，
\(H_{s} - H_{t} + \) (登りのコストの合計)
となる．ここで，登りのコストの合計は負になる．
コストの最大化を考えると，登りのコストの最大化を考えることになる． これは，登りのコストを \(-1\) 倍して正のコストにすれば， 正(または0)のコストの最小化となる． よって Dijikstra 法で求まる．
実装:
登りの合計だけ知りたいので， 下りのコストは \(0\) とする． そうしておかないと，グラフが途切れてしまう．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m;
cin >> n >> m;
vll a(n); rep(i,n) { cin >> a[i]; }
rep(i,m){
ll x,y; cin >> x >> y;
--x, --y;
if(a[x] > a[y]) swap(x,y);
to[x].emplace_back(y, a[y]-a[x]); // 登りの合計のminだけ求める
to[y].emplace_back(x, 0); // 下りは 0とする
}
min_priority_queue<pll> q;
q.push({dis[0]=0,0});
while(q.size()){
auto [cd, cv] = q.top(); q.pop();
for(auto [nv, cost]:to[cv]) {
ll nd = cd + cost;
if(chmin(dis[nv], nd)){
q.push({nd,nv});
}
}
}
ll ans = -INFL;
rep(i,n){
ll x = a[0] - a[i] - dis[i];
chmax(ans, x);
}
cout << ans << endl;
return 0;
}
