文化之旅（culture）

NOIP 2012 复赛普及组真题。本 OJ 采用标准输入输出评测，无需文件重定向。

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一 种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不 同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来 文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。 现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这 位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求 从起点到终点最少需走多少路。

输入格式

输入文件culture.in。 第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家 个数（国家编号为1 到N），文化种数（文化编号为1 到K），道路的条数，以及起点和终点 的编号（保证S 不等于T）； 第二行为N 个整数，每两个整数之间用一个空格隔开，其中第i 个数Ci，表示国家i 的文化为Ci。 接下来的K 行，每行K 个整数，每两个整数之间用一个空格隔开，记第i 行的第j 个数 为aij，aij= 1 表示文化i 排斥外来文化j（i 等于j 时表示排斥相同文化的外来人），aij= 0 表示 不排斥（注意i 排斥j 并不保证j 一定也排斥i）。 接下来的M 行，每行三个整数u，v，d，每两个整数之间用一个空格隔开，表示国家u 与国家v 有一条距离为d 的可双向通行的道路（保证u 不等于v，两个国家之间可能有多条 道路）。

输出格式

输出文件名为culture.out。 输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如 果无解则输出-1）。

样例1

culture.in culture.out 2 2 1 1 2 1 2 0 1 1 0 1 2 10

-1 【输入输出样例说明】 由于到国家2 必须要经过国家1，而国家2 的文明却排斥国家1 的文明，所以不可能到 达国家2。

----PAGE----

普及组

样例2

culture.in culture.out 2 2 1 1 2 1 2 0 1 0 0 1 2 10

10 【输入输出样例说明】 路线为1 -> 2。

数据范围

对于20%的数据，有2≤N≤8，K≤5； 对于30%的数据，有2≤N≤10，K≤5； 对于50%的数据，有2≤N≤20，K≤8； 对于70%的数据，有2≤N≤100，K≤10； 对于100%的数据，有2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u, v≤N，1≤d≤1000， S≠T，1 ≤S, T≤N。

----PAGE----