用的是优先队列的堆优化Dijkstra + 链式前向星

代码如下,我看不出这有任何MLE的可能啊...

#include <bits/stdc++.h>
using namespace std;

struct Med{
    int cost,positive,negative;
    Med(int cost,int positive,int negative):cost(cost),positive(positive),negative(negative){}
};
struct Edge{
    int to,cost;
    Edge(int to,int cost):to(to),cost(cost){}
};
typedef vector<Edge> ve;
typedef vector<Med> vm;
typedef vector<int> vi;

const int max_num_of_sym = 10,maxm = 1e3;
const int max_state = 1 << max_num_of_sym;
int d[max_state];
bool visited[max_state];
ve edges[max_state];
vm meds;

int get_bin_from_line(){
    string line;
    getline(cin,line);
    bitset<max_num_of_sym> b(line);
    return b.to_ulong();
}
int main(){
    #ifdef DEBUG
    freopen("in","r",stdin);
    #endif
    int t,n,m;
    cin >> t;
    while(t--){
        meds.clear();
        cin >> n >> m;
        getchar();
        int src_state = get_bin_from_line();
        for(int i = 0;i < m;i++){
            int cost;
            cin >> cost;
            getchar();
            int positive = get_bin_from_line(),negative = get_bin_from_line();
            meds.emplace_back(cost,positive,negative);
        }
        for(int state = 0;state < (1 << n);state++){
            edges[state].clear();
            for(int med_index = 0;med_index < m;med_index++){
                Med med = meds[med_index];
                int next_state = (state & (~med.positive)) | (med.negative);
                edges[state].emplace_back(next_state,med.cost);
            }
        }
        int dst_state = 0;
        memset(d,-1,sizeof(d));
        memset(visited,false,sizeof(visited));
        auto cmp = [](int x,int y){
            return d[x] > d[y];
        };
        priority_queue<int,vi,decltype(cmp)> Q(cmp);
        auto relax = [&](int state,int dist){
            d[state] = d[state] == -1 ? dist : min(dist,d[state]);
            Q.push(state);
        };
        relax(src_state,0);
        while(!Q.empty()){
            int state_now = Q.top();
            Q.pop();
            visited[state_now] = true;
            if(state_now == dst_state) break;
            for(int i = 0;i < edges[state_now].size();i++){
                Edge E = edges[state_now][i];
                if(visited[E.to] == false){
                    relax(E.to,d[state_now] + E.cost);
                }
            }
        }
        cout << d[dst_state] << endl;
    }
    return 0;
}