/* -*- coding: utf-8 -*- * * 3158.cc: No.3158 Collect Stamps - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 16; const int NBITS = 1 << MAX_N; const int INF = 1 << 30; /* typedef */ /* global variables */ int as[MAX_N], ts[MAX_N][MAX_N]; int bnums[NBITS], dp[NBITS][MAX_N]; /* subroutines */ inline void setmin(int &a, int b) { if (a > b) a = b; } /* main */ int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < k; i++) scanf("%d", as + i), as[i]--; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", ts[i] + j); int nbits = 1 << n; bnums[0] = 0; for (int bits = 1, msb = 1; bits < nbits; bits++) { if ((msb << 1) <= bits) msb <<= 1; bnums[bits] = bnums[bits ^ msb] + 1; } for (int bits = 0; bits < nbits; bits++) fill(dp[bits], dp[bits] + n, INF); for (int i = 0; i < n; i++) dp[1 << i][i] = 0; for (int bits = 0; bits < nbits; bits++) for (int i = 0; i < n; i++) if (dp[bits][i] < INF) for (int j = 0, bj = 1; j < n; j++, bj <<= 1) if (! (bits & bj)) setmin(dp[bits | bj][j], dp[bits][i] + ts[i][j]); int mind = INF; for (int bits = 0; bits < nbits; bits++) if (bnums[bits] >= m) for (int i = 0; i < n; i++) if (dp[bits][i] < INF) for (int j = 0; j < k; j++) setmin(mind, dp[bits][i] + ts[i][as[j]]); printf("%d\n", mind); return 0; }