UVa658 It’s not a Bug, it’s a Feature!(Dijkstra)

题意

给出一个包含n个bug的应用程序，以及m个补丁，每个补丁使用两个字符串表示，第一个串表示补丁针对bug的情况，即哪些bug存在，以及哪些bug不存在，第二个串表示补丁对bug的修复情况，即修复了哪些bug,以及引入哪些bug。补丁还包含修复的时间。问修复这些bug所需要的最短时间

思路

使用Dijkstra算法，使用n表示bug数，bug数限制在20内，初始n个bug全存在，即源点为1<

代码

#include 

using namespace std;

#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)

struct Edge
{
    int from, to, dist;
};

struct HeapNode
{
    int u, d;

    bool operator<(const HeapNode& other) const
    {
        return d > other.d;
    }
};

struct Patch
{
    int present, absent, introduce, remove, time;

    bool canApply(int u) const
    {
        return (u & present) == present && (absent & u) == 0;
    }

    int apply(int u) const
    {
        return (u | introduce) & (~remove);
    }
};

template <size_t SZV, int INF>
struct Dijkstra
{
    int n;
    vector<Patch> patches;
    bool done[SZV];
    int d[SZV];

    void init(int n)
    {
        this-> n = (1 << n);
        patches.clear();
    }

    void dijkstra(int s)
    {
        priority_queue<HeapNode> pq;
        fill_n(done, n, false);
        fill_n(d, n, INF);
        d[s] = 0;
        pq.push({s, 0});

        while (!pq.empty()) {
            HeapNode curNode = pq.top();
            pq.pop();

            int u = curNode.u;
            if (done[u]) {
                continue;
            }

            done[u] = true;
            _for(i, 0, patches.size()) {
                const Patch& p = patches[i];
                if (!p.canApply(u)) {
                    continue;
                }

                int v = p.apply(u);
                if (d[v] > d[u] + p.time) {
                    d[v] = d[u] + p.time;
                    pq.push({v, d[v]});
                }
            }

        }
    }
};



void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

const int MAXN = 20;
const int MAXV = (1 << MAXN) + 4;
const int INF = 1e9;


int n, m;

void toInt(const string& s, int& i1, int& i2)
{
    i1 = i2 = 0;
    _for(i, 0, n) {
        if (s[i] == '+') {
            i1 |= (1 << i);
        }

        if (s[i] == '-') {
            i2 |= (1 << i);
        }
    }
}

Dijkstra<MAXV, INF> solver;

int main()
{
    fastio();

    #ifndef ONLINE_JUDGE
        ifstream fin("f:\\OJ\\uva_in.txt");
        streambuf* back = cin.rdbuf(fin.rdbuf());
    #endif


    int kase = 1;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) {
            break;
        }

        //cout << "n:" << n << " m:" << m << endl;

        solver.init(n);

        string buf1, buf2;
        Patch patch;
        _for(i, 0, m) {
            cin >> patch.time >> buf1 >> buf2;
            toInt(buf1, patch.present, patch.absent);
            toInt(buf2, patch.introduce, patch.remove);
            solver.patches.push_back(patch);
        }

        /*
        for (int i = 0; i < solver.patches.size(); i++) {
            const Patch& patch = solver.patches[i];
            cout << patch.present << " " << patch.absent << " " << patch.introduce << " " << patch.remove << endl;
        }
        */

        solver.dijkstra(solver.n - 1);

        cout << "Product " << kase++ << endl;
        if (solver.d[0] == INF) {
            cout << "Bugs cannot be fixed." << endl;
        } else {
            cout << "Fastest sequence takes " << solver.d[0] << " seconds." << endl;
        }

        cout << endl;

    }

    #ifndef ONLINE_JUDGE
        cin.rdbuf(back);
    #endif

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

注意

因为在代码中初始节点数为1<<20-1，如果直接在栈上即main函数中创建Dijkstra类，由于栈空间限制，会出错，所以需要设置为全局变量