CodeforcesRound#321(Div.2)KefaandDishes状压+spfa

#include
#include
#include
#include
#include
#define MAX_S 1<<19
#define MAX_N 22
using namespace std;typedef long long ll;struct edge {
public:int to;ll cost;edge(int t, ll c) : to(t), cost(c) { }edge() { }
};vector G[MAX_N];
ll g[MAX_N][MAX_N];
ll a[MAX_N];
int n,m,k;int ones[MAX_S];ll dp[MAX_N][MAX_S];struct node {
public:ll s;int u;node(ll ss, int uu) : s(ss), u(uu) { }node() { }
};queue que;
bool inQue[MAX_N][MAX_S];int main() {cin.sync_with_stdio(false);cin >> n >> m >> k;for (int i &＃61; 0; i <(1 <) {int x &＃61; i;while (x)ones[i] &＃43;&＃61; (x & 1), x >>&＃61; 1;}for (int i &＃61; 0; i )cin >> a[i];for (int i &＃61; 0; i ) {int x, y;ll c;cin >> x >> y >> c;x--, y--;g[y][x] &＃61; c;}for (int i &＃61; 0; i )for (int j &＃61; 0; j )G[i].push_back(edge(j, g[i][j]));ll ans &＃61; 0;for (int i &＃61; 0; i ) {dp[i][1 < a[i];que.push(node(1 << i, i));inQue[i][1 <1;}while (!que.empty()) {node now &＃61; que.front();que.pop();ll s &＃61; now.s;int u &＃61; now.u;inQue[u][s] &＃61; 0;for (int i &＃61; 0; i ) {int v &＃61; G[u][i].to;ll c &＃61; G[u][i].cost;if (s & (1 <continue;ll ns &＃61; s | (1 << v);if (ones[ns] > m)continue;if (dp[v][ns] c) {dp[v][ns] &＃61; dp[u][s] &＃43; a[v] &＃43; c;que.push(node(ns, v));inQue[v][ns] &＃61; 1;}}}for (int i &＃61; 0; i )for (int s &＃61; 0; s <(1 <)if (ones[s] &＃61;&＃61; m)ans &＃61; max(ans, dp[i][s]);cout < endl;return 0;
}