TLE了一个点?

第9个点T了。。
什么原因?

#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; 
}

0 条评论

目前还没有评论...

信息

ID
1019
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1525
已通过
462
通过率
30%
被复制
1
上传者