亚洲区天津赛区网络预选赛的一道题，简单的搜索，但是搜索的时候最好把开始点1拆为两个节点，如果1不是必经节点，那么拆不拆都无所谓，如果1是必经节点，那么在刚开始在1的时候选择工作还是到最后再工作就要分情况，所以要进行拆点。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N 105 5 #define inf 0x7fffffff 6 using namespace std; 7 int map[N][N]; 8 int c[N],d[N],f[18]; 9 int h;10 bool dfs(int u,int mon,int state)11 {12     if(mon
         
          w)46             map[u][v]=map[v][u]=w;47         }48         for(k=1;k<=n;k++)49         for(i=1;i<=n;i++)50         for(j=1;j<=n;j++)51         {52             if(map[i][k]!=inf&&map[k][j]!=inf&&map[i][k]+map[k][j]