ダイクストラ法は、辺の重みが非負のときに始点からの最短距離を求める次のようなアルゴリズムです。

while 距離が未確定の頂点がある:
    未確定の頂点のうち距離が最小の頂点の距離を確定する
    その頂点と辺で結ばれた頂点の距離を更新する

ダイクストラ法の正当性の証明と同様に考えれば、この問題では次のようなアルゴリズムが正当だと分かります。

while スコアが未確定の頂点がある:
    未確定の頂点 v のうち A[v] が最も小さく、その中でスコアが最大の頂点のスコアを確定する
    その頂点と辺で結ばれた頂点のスコアを更新する

ダイクストラ法と同様の実装により、このアルゴリズムは十分高速に動作します。 例えばペア (A[v], 頂点 v のスコアの(-1)倍) をキーとして優先度つきキューを使えばよいです。