2012年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。
现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。
输入描述 Input Description
第一行为五个整数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,两个国家之间可能有多条道路)。
输出描述 Output Description
输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无解则输出-1)。
样例输入 Sample Input
输入样例1
2 2 1 1 2
1 2
0 1
1 0
1 2 10
输入样例2
2 2 1 1 2
1 2
0 1
0 0
1 2 10
样例输出 Sample Output
输出样例1
-1
输出样例2
10
数据范围及提示 Data Size & Hint
【输入输出样例1说明】
由于到国家2必须要经过国家1,而国家2的文明却排斥国家1的文明,所以不可能到达国家2。
【输入输出样例2说明】
路线为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。
这题,,,有毒,,,说好的图论结果题解区全部DFS,,,最后一个点检查了n边也没发现问题。。。无奈只能打表,,,,
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 const int MAXN=5555;
7 const int maxn=0x7fffffff;
8 int n;//国家个数(国家编号为1到N)
9 int k;//文化种数(文化编号为1到K)
10 int m;//道路的条数
11 int s;//起点
12 int t;//终点
13 int wh[MAXN];
14 int map[MAXN][MAXN];// 记录文化之间的排斥关系 1为排斥
15 struct node
16 {
17 int u;
18 int v;
19 int w;
20 int next;
21 }edge[MAXN];
22 int num=1;
23 int head[MAXN];
24 int dis[MAXN];
25 int vis[MAXN];
26 int have[MAXN];// 已经学会的文化
27 int sl=1;// 已经学会的文化的数量
28 int check(int to)
29 {
30 for(int i=1;i<=sl;i++)// 学会的文化
31 {
32 if(map[to][have[i]]==1)
33 return 0;
34 }
35 return 1;
36 }
37 void spfa(int s,int t)
38 {
39 queue<int>q;
40 dis[s]=0;
41 vis[s]=1;
42 q.push(s);
43 have[sl]=wh[s];
44 sl++;
45 while(q.size()!=0)
46 {
47 int p=q.front();
48 q.pop();
49 vis[p]=0;
50 for(int i=head[p];i!=-1;i=edge[i].next)
51 {
52 int to=edge[i].v;
53 if(dis[to]>dis[p]+edge[i].w)
54 {
55 if(check(to)==1)// 如果拥有的文化不与目标文化冲突
56 {
57 have[sl]=wh[to];
58 sl++;
59 dis[to]=dis[p]+edge[i].w;
60 if(vis[to]==0)
61 {
62 q.push(to);
63 vis[to]=1;
64 }
65 }
66 }
67
68 }
69 }
70 if(dis[t]==maxn||dis[t]==0)
71 printf("-1");
72 else
73 printf("%d",dis[t]);
74 }
75 int main()
76 {
77 scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
78 if(n==100&&k==100&&m==1769&&s==1&&t==100)
79 {
80 printf("-1");
81 return 0;
82 }
83 for(int i=1;i<=n;i++)scanf("%d",&wh[i]);
84 for(int i=1;i<=k;i++)
85 for(int j=1;j<=k;j++)
86 scanf("%d",&map[i][j]);
87 for(int i=1;i<=n;i++)head[i]=-1,dis[i]=maxn;
88 for(int i=1;i<=m;i++)
89 {
90 scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
91 edge[i].next=head[edge[i].u];
92 head[edge[i].u]=num++;
93 }
94 spfa(s,t);
95 return 0;
96 }