[题解] uva 658 It's not a Bug, it's a Feature! (dijkstra最短路)

- 传送门 -

　https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=599

# 658 - It's not a Bug, it's a Feature! Time limit: 3.000 seconds | [Root](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=0) | [](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=submit_problem&problemid=599&category=) [](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=599&category=) [](https://www.udebug.com/UVa/658) [](https://uva.onlinejudge.org/external/6/658.pdf) | ###(题面见pdf) 　 ### - 题意 - 　输入 n , m 表示我们有一个长为 n , 每一位上都有 bug 的数列, m 个操作. 　每个操作形如下: 　T 000--+0+ ++++00-- 　T表示完成该操作的时间, 第一个字符串表示初始状态, 第二个表示完成状态. 　初始状态中 + 表示该位一定要有bug, - 表示一定不能有, 0 表示随意. 　完成状态中, + 表示该位有bug, - 表示没有, 0 表示与初始状态一致. 　求使得每一位上都没有bug的最小时间. 　 ### - 思路 - 　二进制表示每一位上的bug的有无, 每种情况对应一个节点(初始节点为(1 << n) - 1, 表示0 ~ n-1位上每一位都有bug(都是1)), 对于每次考虑到的节点, 我们扫一遍每种操作, 将满足要求的操作套上去, 尝试更新目标状态的节点.

　细节见代码.
　
　PS:
　dijkstra慢如狗...用SPFA的快如闪电
　

- 代码 -

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 20;
const int M = 100 + 5;
const int inf = 0x3f3f3f3f;

struct point {
	int bug, dist;
	bool operator < (const point &y) const {
		return dist > y.dist;
//priority_queue维护大根堆, 重定义'<', 插入的数比父亲小则满足条件, 往上交换...其实没有搞懂...以后还是用pair好了
	}
};

priority_queue<point> Q;

int TI[M], VIS[(1<<N) + 5], DIS[(1<<N) + 5];
char BG[M][25], ED[M][25];

int n, m;

int dijkstra() {
	for (int i = 0; i < (1<<N); ++i) {
		VIS[i] = 0;
		DIS[i] = inf;
	}
	while (!Q.empty())
		Q.pop();
	point st;
	st.bug = (1 << n) - 1;
	st.dist = 0;
	DIS[st.bug] = 0;
	Q.push(st);
	while (!Q.empty()) {
		point x = Q.top();
		Q.pop();
		if (VIS[x.bug]) continue;
		VIS[x.bug] = 1;
		if (!x.bug) return x.dist;
		for (int i = 1; i <= m; ++i) {
			bool flag = true;
			for (int j = 0; j < n; ++j) {
				if (BG[i][j] == '-' && (x.bug&(1<<j))) { flag = false; break; }
				if (BG[i][j] == '+' && !(x.bug&(1<<j))) { flag = false; break; }
			}
			if (!flag) continue;
			point y = x;
			y.dist += TI[i];
			for (int j = 0; j < n; ++j) {
				if (ED[i][j] == '-') y.bug &= ~(1<<j);
				if (ED[i][j] == '+') y.bug |= (1<<j);
			}
			if (!VIS[y.bug] && y.dist < DIS[y.bug]) {
				DIS[y.bug] = y.dist;
				Q.push(y);
			}
		}
	}
	return -1;
}

int main() {
	int cas = 0;
	while (scanf("%d%d", &n, &m) != EOF && n && m) {
//		if (cas) printf("
");
//		cas++;
		printf("Product %d
", ++cas);
		for (int i = 1; i <= m; ++i)
			scanf("%d%s%s", &TI[i], BG[i], ED[i]);
		int ans = dijkstra();
		if (ans == -1) printf("Bugs cannot be fixed.

");
	    else printf("Fastest sequence takes %d seconds.

", ans); //uva再次玄学格式
	}
	return 0;
}