# TLE了一个点？

``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const double eps=1e-8;

int n,m;
int d[(1<<15)+10];
int cost[101];
string a[101],b[101];
struct node {
string s;
int d;
bool operator<(const node a) const {
return d<a.d;
}
};
priority_queue<node> Q;
int turn(string s) {
int res=0;
for (int i=0;i<s.size();i++) {
res=res*2+s[i]-'0';
}
return res;
}
void Dijkstra() {
node x;
x.s="";
FOR(i,n) x.s+='1';
x.d=0;
Q.push(x);
while (Q.size()) {
x=Q.top();Q.pop();
if (x.d>d[turn(x.s)]) continue;
FOR(i,m) {
bool flag=1;
for (int j=0;j<a[i].size();j++) {
if (a[i][j]=='+'&&x.s[j]=='0'||a[i][j]=='-'&&x.s[j]=='1') {
flag=0;
break;
}
}
if (!flag) continue;
string ss=x.s;
for (int j=0;j<a[i].size();j++) {
if (b[i][j]=='+') ss[j]='1';
if (b[i][j]=='-') ss[j]='0';
}
if (d[turn(ss)]>x.d+cost[i]) {
Q.push(node{ss,x.d+cost[i]});
d[turn(ss)]=x.d+cost[i];
}
}
}
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin>>n>>m;
memset(d,0x3f,sizeof d);
FOR(i,m) {
cin>>cost[i]>>a[i]>>b[i];
}
Dijkstra();
if (d[0]==inf) cout<<"0";
else {
cout<<d[0];
}
cout<<endl;
return 0;
}
``````

ID
1019

6

1526

463

30%

3