汉尼拔：题解

其实不难（暴力就能过），但通过标签阅读题目可知要用状压DP，注意这题出题者有点bsr，时间很极限，可能要多交几次
代码（码风奇丑，那二十行fill是用来省最后一毫秒的，也防复制G，不点名）（我原名lyy014，汉尼拔最优解）

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
#define read() ({ \
    register int x = 0; \
    register char c; \
    do { c = getchar(); } while (c < '0' || c > '9'); \
    do { x = x * 10 + (c ^ 48); c = getchar(); } while (c >= '0' && c <= '9'); \
    x; \
})
#define write(x) do { \
    static char buf[20]; \
    int pos = 0; \
    long long _x = x; \
    if (_x < 0) { putchar('-'); _x = -_x; } \
    if (_x == 0) { putchar('0'); break; } \
    while (_x > 0) { buf[pos++] = _x % 10 + '0'; _x /= 10; } \
    while (pos > 0) putchar(buf[--pos]); \
} while(0)


const long long INF = 1e18;
const int MAXN = 505;
const int MAXK = 12;
const int MAXMASK = 1 << MAXK;
const int MAXADJ = 1005;

int n, m, k;
int type[MAXN];
int adj_v[MAXN][MAXADJ];
int adj_c[MAXN][MAXADJ];
int adj_siz[MAXN];
long long dp[MAXMASK][MAXN];
bool inque[MAXMASK][MAXN];
signed main() {
    n = read();
    m = read();
    k = read();
    memset(adj_siz, 0, sizeof(adj_siz));
    for (int i = 1; i <= n; ++i) {
        type[i] = read() - 1;
        if (type[i] < 0 || type[i] >= k) {
            type[i] = 0;
        }
    }
    for (int i = 0; i < m; ++i) {
        int a = read();
        int b = read();
        int c = read();
        if (c < 0) c = 0;
        adj_v[a][adj_siz[a]] = b;
        adj_c[a][adj_siz[a]++] = c;
        adj_v[b][adj_siz[b]] = a;
        adj_c[b][adj_siz[b]++] = c;
    }
    fill(dp[0], dp[0] + n + 1, INF);
    fill(dp[1], dp[1] + n + 1, INF);
    fill(dp[2], dp[2] + n + 1, INF);
    fill(dp[3], dp[3] + n + 1, INF);
    fill(dp[4], dp[4] + n + 1, INF);
    fill(dp[5], dp[5] + n + 1, INF);
    fill(dp[6], dp[6] + n + 1, INF);
    fill(dp[7], dp[7] + n + 1, INF);
    fill(dp[8], dp[8] + n + 1, INF);
    fill(dp[9], dp[9] + n + 1, INF);
    fill(dp[10], dp[10] + n + 1, INF);
    fill(dp[11], dp[11] + n + 1, INF);
    fill(dp[12], dp[12] + n + 1, INF);
    fill(dp[13], dp[13] + n + 1, INF);
    fill(dp[14], dp[14] + n + 1, INF);
    fill(dp[15], dp[15] + n + 1, INF);
    fill(dp[16], dp[16] + n + 1, INF);
    fill(dp[17], dp[17] + n + 1, INF);
    fill(dp[18], dp[18] + n + 1, INF);
    fill(dp[19], dp[19] + n + 1, INF);
    fill(dp[20], dp[20] + n + 1, INF);
    for (int mask = 21; mask < (1 << k); ++mask) {
        fill(dp[mask], dp[mask] + n + 1, INF);
    }
    for (int u = 1; u <= n; ++u) {
        dp[1 << type[u]][u] = 0;
    }
    for (int mask = 1; mask < (1 << k); ++mask) {
        for (int submask = (mask - 1) & mask; submask > 0; submask = (submask - 1) & mask) {
            int other = mask ^ submask;
            if (other == 0) continue;
            for (int u = 1; u <= n; ++u) {
                if (dp[submask][u] != INF && dp[other][u] != INF) {
                    dp[mask][u] = min(dp[mask][u], dp[submask][u] + dp[other][u]);
                }
            }
        }
        queue<int> q;
        memset(inque[mask], 0, sizeof(inque[mask]));
        for (int u = 1; u <= n; ++u) {
            if (dp[mask][u] != INF) {
                q.push(u);
                inque[mask][u] = true;
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inque[mask][u] = false;
            for (int i = 0; i < adj_siz[u]; ++i) {
                int v = adj_v[u][i];
                int c = adj_c[u][i];
                if (dp[mask][u] + c < dp[mask][v]) {
                    dp[mask][v] = dp[mask][u] + c;
                    if (!inque[mask][v]) {
                        q.push(v);
                        inque[mask][v] = true;
                    }
                }
            }
        }
    }
    if (k == 0) {
        write(0);
        putchar('\n');
        return 0;
    }
    int full_mask = (1 << k) - 1;
    long long ans = INF;
    for (int u = 1; u <= n; ++u) {
        ans = min(ans, dp[full_mask][u]);
    }
    write(ans == INF ? -1 : ans);
    putchar('\n');
    
    return 0;
}