1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define M 301 6 #define N 4000001 7  8 int n, m; 9 int b1[M], b2[M], f1[M], f2[M], a[M], dis[N];10 bool vis[N];11 12 inline void spfa()13 {14     int i, v, u;15     std::queue <int> q;16     memset(dis, 0x33, sizeof(dis));17     q.push((1 << n) - 1);18     dis[(1 << n) - 1] = 0;19     while(!q.empty())20     {21         u = q.front(), q.pop();22         vis[u] = 0;23         for(i = 1; i <= m; i++)24             if((u | b1[i]) == u && !(u & b2[i]))25             {26                 v = u ^ (u & f1[i]) | f2[i];27                 if(dis[v] > dis[u] + a[i])28                 {29                     dis[v] = dis[u] + a[i];30                     if(!vis[v])31                     {32                         q.push(v);33                         vis[v] = 1;34                     }35                 }36             }37     }38 }39 40 int main()41 {42     int i, j;43     char s1[M], s2[M];44     scanf("%d %d", &n, &m);45     for(i = 1; i <= m; i++)46     {47         scanf("%d %s %s", &a[i], s1, s2);48         for(j = 0; j < n; j++)49         {50             if(s1[j] == ‘+‘) b1[i] |= 1 << j;51             if(s1[j] == ‘-‘) b2[i] |= 1 << j;52             if(s2[j] == ‘-‘) f1[i] |= 1 << j;53             if(s2[j] == ‘+‘) f2[i] |= 1 << j;54         }55     }56     spfa();57     dis[0] == dis[1 << n] ? puts("0") : printf("%d\n", dis[0]);58     return 0;59 }