1316 文化之旅 2012年NOIP全国联赛普及组

1316 文化之旅

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

leetcode 860 —柠檬水找零(简单题)

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

1304
来自专栏域名资讯

3杂域名22k.com以六位数被售出

随着短域名资源的稀缺,像三杂这类短域名自然成为了抢手货,未来的发展潜力不容小觑,是投资的最佳品种之一。借字符简单、建站不受限制、简洁易记等优势,在米...

2230
来自专栏小樱的经验随笔

BZOJ 3668: [Noi2014]起床困难综合症【贪心】

3668: [Noi2014]起床困难综合症 Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 2326  So...

2724
来自专栏chenjx85的技术专栏

leetcode-860-柠檬水找零

1274
来自专栏desperate633

[编程题] 赶去公司代码

终于到周末啦!小易走在市区的街道上准备找朋友聚会,突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域,每条街道假设坐标是(X,...

702
来自专栏落影的专栏

程序员进阶之算法练习(三十一)

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。

1463
来自专栏swag code

荷兰国旗-快排应用

”荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。

892
来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

3387
来自专栏落影的专栏

程序员进阶之算法练习(十一)有感而发

前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

37010
来自专栏ACM算法日常

水果(STL+排序)- HDU 1263

夏天来了~~好开心啊,呵呵,好多好多水果~~ Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样J...

871

扫码关注云+社区