文化之旅

1316 文化之旅

二〇一二年NOIP全国联赛普及组

时间限制: 1 s

空间范围: 128000 KB

题目等级 : 黄金 高尔德(Gold)(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)。

样例输入 萨姆ple 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

 

样例输出 萨姆(Sam)ple 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;

88bifa必发娱乐,对于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 }

 

 

相关文章