You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
57 lines
1.7 KiB
C++
57 lines
1.7 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
inline void setBit(int &x, int p) { x |= (1 << p); }
|
|
inline int getBit(int x, int p) { return x >> p & 1; }
|
|
inline void flipBit(int &x, int p) { x ^= (1 << p); }
|
|
const int N = 105;
|
|
int dis[1 << 20 | 1];
|
|
bool inq[1 << 20 | 1];
|
|
int b1[N], b2[N], f1[N], f2[N], t[N];
|
|
int main()
|
|
{
|
|
int n, m, mask;
|
|
scanf("%d%d", &n, &m);
|
|
mask = (1 << n) - 1;
|
|
for (int i = 0; i < m; i++)
|
|
{
|
|
char buf1[N], buf2[N];
|
|
scanf("%d%s%s", t + i, buf1, buf2);
|
|
for (int k = 0; k < n; k++)
|
|
{
|
|
if (buf1[k] == '+') setBit(b1[i], k);
|
|
if (buf1[k] == '-') setBit(b2[i], k);
|
|
}
|
|
for (int k = 0; k < n; k++)
|
|
{
|
|
if (buf2[k] == '-') setBit(f1[i], k);
|
|
if (buf2[k] == '+') setBit(f2[i], k);
|
|
}
|
|
}
|
|
memset(dis, 0x3f, sizeof(dis));
|
|
queue<int> Q;
|
|
Q.push(mask);
|
|
dis[mask] = 0;
|
|
for (int cur; !Q.empty(); Q.pop())
|
|
{
|
|
inq[cur = Q.front()] = false;
|
|
for (int i = 0; i < m; i++)
|
|
if ((cur & b1[i]) == b1[i] && (cur & b2[i]) == 0)
|
|
{
|
|
int nxt = (cur & ~f1[i]) | f2[i];
|
|
if (dis[nxt] > dis[cur] + t[i])
|
|
{
|
|
dis[nxt] = dis[cur] + t[i];
|
|
if (!inq[nxt])
|
|
{
|
|
inq[nxt] = true;
|
|
Q.push(nxt);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if (dis[0] > 0x3f3f3f3f >> 1) dis[0] = 0;
|
|
printf("%d", dis[0]);
|
|
return 0;
|
|
} |