用spfa，和dp是一样的。转移只和最后一个吃的dish和吃了哪些有关。

把松弛改成变长。因为是DAG，所以一定没环。操作最多有84934656，514ms跑过，实际远远没这么多。

脑补过一下费用流，但是限制流量不能保证吃到m个菜

#include
     
      using namespace std;typedef pair
      
        nd;typedef long long ll;#define fi first#define se secondint n,m,a[18];int g[18][18];const int maxs = 1<<18;ll d[maxs][18];bool vis[maxs][18];inline int bitcount(int s){    int ct = 0;    while(s){        ct += s&1;        s >>= 1;    }    return ct;}ll spfa(){    queue
       
        q;    ll ans = 0;    for(int i = 0; i < n; i++){        q.push(nd(1<
        
         >i)) continue;            int ns = 1<