记录编号	352127	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-11-16 21:28:20	内存使用	0.49 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
 
const int maxnumber = 110;
int n, k, m, s, t;
// 点数 文化数 边数 起点 终点
struct Edge
{
	int to, w, next;
}edges[maxnumber * maxnumber];
int head[maxnumber], tot;
int type[maxnumber], G[maxnumber][maxnumber];
struct Node
{
	int pos;
	set <int> S;// 记录走过的文化
	inline Node(const int& a, const set <int>& t): pos(a), S(t) {}
};
queue <Node> Q;
int dis[maxnumber];
 
inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}
 
inline void BFS()
{
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	set <int> S;
	S.insert(type[1]);
	Q.push(Node(s, S));
	while (!Q.empty()) {
		Node front = Q.front(); Q.pop();
		int pos = front.pos;
		set <int> S = front.S;
		for (int i = head[pos]; i; i = edges[i].next) {
			int to = edges[i].to, w = edges[i].w;
			bool flag = 0;
			for (int j = 1; j <= k; ++j) {
				if (G[type[to]][j] && S.count(j)) { flag = 1; break; }
			}// 文化冲突
			if (!flag) {
				if (dis[to] > dis[pos] + w) {
					dis[to] = dis[pos] + w;
					set <int> tmp = S;
					tmp.insert(type[to]);
					Q.push(Node(to, tmp));
				}
			}
		}
	}
	if (dis[t] == 0x3f3f3f3f) printf("-1\n");
	else printf("%d\n", dis[t]);
}
 
#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("culture.in", "r", stdin); freopen("culture.out", "w", stdout);
#endif
 
	int from, to, w;
	scanf("%d%d%d%d%d", &n, &k, &m, &s, &t);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &type[i]);
	for (int i = 1; i <= k; ++i)
		for (int j = 1; j <= k; ++j)
			scanf("%d", &G[i][j]);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &from, &to, &w);
		AddEdge(from, to, w);
		AddEdge(to, from, w);
	}
	BFS();
 
#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif
 
	return 0;
}