【输入输出样例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 }
