阿里9.25 笔试第二题代码。

#include<bits/stdc++.h>
//2020/9/25 钟思维
using namespace std;
int ju(int j,int n) {
    int re = 0;
    for (int i = 0; i <n ; i++) {
        if ((j >> i) & 1 == 1)re++;
    }
    return re;
}
int main() {
    int n, m;
    long k;
    cin >> n >> m >> k;
    long l = 1 << n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<long>> v(n+1, vector<long>(n+1,0));
    for (int i = 0; i < k; i++) {
        long x, y, c;
        cin >> x >> y >> c;
      v[x-1][y-1] = c;
    }
    long re = 0;
    vector<vector<long>> vv(n, vector<long>(l, 0));
    for (int j = 0; j < n; j++) {
        vv[j][0] = a[j];
    }
    for (int i = 1; i < l; i++) {
        for (int j = 0; j < n; j++) {
            int k1 = ju(i, n);
            if (k1>= m)continue;
            if (((i >> j) &1)==0) {
                for (int k = 0; k < n; k++) {
                    if (((i >> k) & 1 == 1)) {
                        vv[j][i]=max(vv[j][i],a[j]+v[j][k]+vv[k][i^(1<<k)]);
                    }

                }
            }
            if (k1 == m - 1)re = max(re, vv[j][i]);
        }
    }
    cout << re;
}