“网络流”好题。。。

为啥这个题会出现在网络流24题里呢QAQ我真的按照网络流想的建了一个2^n个点的2^n*n边的图。。。然后一想网络流再怎么跑都跑不出1e6点数1e6边数的非分层图吧。。。弃疗看题解md怎么是状压+最短路qaq

就是状压状态然后dp因为1e6的状态每次转移又有100所以最短路更新就好了。

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int f[1048576];struct node{	int x,dis;	node(){}	node(int _x,int _dis){x=_x,dis=_dis;}};bool operator <(node a,node b){return a.dis>b.dis;}priority_queue
         
           que;bool vis[1048576];int bug[101][2],fix[101][2],n,m,tm[101];void dij(){ memset(f,48,sizeof(f));//printf("%d\n",f[0]); f[(1<
          
           <
           
            f[x]+tm[i]) f[to]=f[x]+tm[i],que.push(node(to,f[to])); } }}char ch[21];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d",&tm[i]); scanf("%s",ch); int len=strlen(ch); for(int j=0;j