Submission #1589123

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, K;
vector<int> d, x, y;
int G[50][50] = {};

ll dfs(int t, ll sum, int used) {
  used = used | 1 << t;

  ll res = 0;
  bool ng = true;
  for (int i = 0; i < n; i++) {
    if (!G[t][i] || (used >> i & 1)) continue;
    res = max(res, dfs(i, sum + d[t], used));
    ng = false;
  }

  if (ng) return sum + d[t];
  return res;
}

int main(void) {
  cin >> n >> K;

  d.resize(n);
  x.resize(K);
  y.resize(K);
  for (int i = 0; i < n; i++) {
    cin >> d[i];
  }
  for (int i = 0; i < K; i++) {
    cin >> x[i] >> y[i];
    x[i]--, y[i]--;
    G[x[i]][y[i]] = G[y[i]][x[i]] = 1;
  }

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans = max(ans, dfs(i, 0, 0));
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result