主题素材陈述 Description

1316 文化之旅

贰零壹叁年NOIP全国际缔盟赛普遍组

时限: 1 s

空间限制: 12捌仟 KB

标题等第 : 黄金 高尔德

 

 

 

 

难点陈说 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 }

 

 

相关文章

网站地图xml地图