解法

概要

グラフにして貪欲。 終了時の状態を考えると、部分的な操作にも点数を付けることができる。 $O(N \log N + M)$。

詳細

制約の関係をとりあえずグラフにする。 すると次のような問題になる:

頂点数$N$で辺数$M$の単純無向グラフ$G$があり、頂点$i$には重み$s_i$、辺$j$には重み$c_j$が定まっている。 $2$人で交互に頂点に白黒の色を塗り、塗った頂点の重み、両端を塗った辺の重みが得点。 これが大きい方の勝ち。

一般のグラフで$N \le 10^5$なので貪欲や偶奇で解けてほしい。 さてここでこのゲームの終了時の状態を眺める。 両端が異なる色で塗られている辺はどちらにとっても$0$点であるが、これを両方に$c_i / 2$点としても変わらない。 すると頂点と頂点の間の依存関係が切れ、頂点を$s_i + \sum _ {(i, j) \in E} c_j / 2$の順で貪欲に取ればよいことになる。

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

bool solve(int n, int m, vector<int> const & s, vector<vector<pair<int, int> > > const & g) {
    vector<ll> score(n);
    REP (i, n) {
        score[i] = 2 * s[i];
        for (auto edge : g[i]) {
            int j, cost; tie(j, cost) = edge;
            score[i] += cost;
        }
    }
    vector<int> order(n);
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) { return score[i] > score[j]; });
    ll first = 0, second = 0;
    REP (i, n) {
        (i % 2 == 0 ? first : second) += score[order[i]];
    }
    return first > second;
}

int main() {
    int n, m; cin >> n >> m;
    vector<int> s(n);
    REP (i, n) cin >> s[i];
    vector<vector<pair<int, int> > > g(n);
    REP (j, m) {
        int a, b, c; cin >> a >> b >> c;
        -- a; -- b;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    bool winner = solve(n, m, s, g);
    cout << (winner ? "First" : "Second") << endl;
    return 0;
}