まず、楽しさの \(-1\) 倍をコストとみなすことで、問題文は次のような最短経路の問題に言い換えることができます。

• \(N\) 頂点 \(2M\) 辺の有向グラフが与えられる。
• 各頂点には頂点ごとに標高 \(H_i\) という値が定まっている。
• 各 \(1\leq i\leq M\) について、\((U_i,V_i)\)の標高の高い方, 低い方をぞれぞれ\(X_i\), \(Y_i\) として、頂点 \(X_i\) から頂点 \(Y_i\) にはコスト \((H_{Y_i}-H_{X_i}) (\leq 0)\) の辺が、頂点 \(Y_i\) から頂点 \(X_i\) にはコスト \(2(H_{X_i}-H_{Y_i}) (\geq0)\) の辺が、張られている。
• (辺を通じてどの頂点からどの頂点へも移動可能である)
• 頂点 \(1\) からの最小移動コスト(負にもなり得る)が最小となる頂点のその最小移動コストを求めよ。(=各頂点について頂点 \(1\) からの最小移動コストを求め、全頂点の中でその最小値を求めよ。)

この問題に直接ダイクストラ法を用いることはできません。 なぜなら、このグラフはコストが負の辺が含まれているからです。 一方で、ベルマンフォード法では計算量が \(O(NM)\) となり間に合いません。そこで、ポテンシャルを用いてこの問題をダイクストラ法が適用できる形にすることを考えます。

具体的には、高橋君に対して (楽しさ)+(現在いる地点の標高) という量を考えます。各広場について、その広場で移動を終えた時のその値の最大値が求まれば、その値からその広場の標高を差し引いた値を広場ごとに出して、最大を取れば答えが求まります。よって、 (楽しさ)+(現在いる地点の標高) の \(-1\) 倍をコストとみなして、次のような問題に言い換えます。

• \(N\) 頂点 \(2M\) 辺の有向グラフが与えられる。
• 各頂点には頂点ごとに標高 \(H_i\) という値が定まっている。
• 各 \(1\leq i\leq M\) について、\((U_i,V_i)\)の標高の高い方, 低い方をぞれぞれ\(X_i\), \(Y_i\) として、頂点 \(X_i\) から頂点 \(Y_i\) にはコスト \(0\) の辺が、頂点 \(Y_i\) から頂点 \(X_i\) にはコスト \((H_{X_i}-H_{Y_i}) (\geq0)\) の辺が、張られている。
• (辺を通じてどの頂点からどの頂点へも移動可能である)
• 各頂点について頂点 \(1\) からの最小移動コストに \(H_i\) を加えたものを求め、全頂点の中でその最小値を求めよ。

この問題はダイクストラ法によって頂点 \(1\) から各頂点への最短経路を求め、そのコストに \(H_i\) を加えたものについての max を取れば良いです。よって、\(O(N\log M)\) でこの問題を解く事が出来ました。

c++による実装例:

#include <bits/stdc++.h>
using namespace std;

#define N 200010
#define INF (long long)2e+18

using namespace std;

int main(void) {
	int n, m;
	long long h[N];
	vector<pair<int, long long> >e[N];

	priority_queue<pair<long long, int> >pq;
	pair<long long, int> p;
	long long d[N];

	int k, x, y;
	long long ans;

	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> h[i];
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		x--;
		y--;
		e[x].push_back({ y,max(h[y] - h[x],(long long)0) });
		e[y].push_back({ x,max(h[x] - h[y],(long long)0) });
	}

	for (int i = 0; i < n; i++)d[i] = INF;
	d[0] = 0;
	ans = 0;
	pq.push({ -d[0],0 });

	for (int i = 0; i < n; i++) {
			p = pq.top();
		while (d[p.second] < -p.first) {
				pq.pop();
				p = pq.top();
		}
		pq.pop();
		k = p.second;
		ans = max(ans, h[0] - h[k] - d[k]);
		for (int i = 0; i < e[k].size(); i++) {
			if (d[e[k][i].first] > (d[k] + e[k][i].second)) {
				d[e[k][i].first] = d[k] + e[k][i].second;
				pq.push({ -d[e[k][i].first],e[k][i].first });
			}
		}
	}

	cout << ans << endl;
	return 0;
}