#include #include #include #include #include #include #include #include using namespace std; ifstream cin("fart.in"); ofstream cout("fart.out"); bitset<20> cities[15],adj[15][15]; int n,m,k,minn; bool viz[15],trueviz[15]; bool verify(int mask) { bitset<20> bb; for(int i=0;i masti=(cities[1]&bb); queue q; int ok=1; memset(trueviz,0,sizeof(trueviz)); trueviz[1]=1; while(ok){ ok=0; memset(viz,0,sizeof(viz)); q.push(1); while(!q.empty()) { int x=q.front(); for(int i=1;i<=n;i++) if(viz[i]==false&&((adj[x][i]&masti)==adj[x][i])) { viz[i]=1; q.push(i); masti|=(bb&cities[i]); } if(!trueviz[x]) { ok++; trueviz[x]=1; } q.pop(); } } if(trueviz[n]) return true; return false; } void combos(int mask, int set, int l) { if(l==k) { if(verify(mask)) minn=min(minn,set); return; } combos(mask,set,l+1); combos(mask+(1<>n>>m>>k; for(int i=1;i<=n;i++) cin>>cities[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) adj[i][j].set(); for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; cin>>adj[a][b]; adj[b][a]=adj[a][b]; } combos(0,0,0); cout<