文化之旅,二零一一年NOIP全国际联盟赛广泛组

2019-08-24 14:45 来源:未知

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=1001;
 5 const int maxn=9999999;
 6 int map[N][N];
 7 int n,k,m,s,t; // n国家数,k 文化数,m 道路数 , 
 8 int K[N];
 9 int OK[N][N];//文化排斥 
10 int main()
11 {
12     cin>>n>>k>>m>>s>>t;//7 4 4 1 3
13     for(int i=1;i<=n;i  )
14      {
15          for(int j=1;j<=n;j  )
16           {
17               map[i][j]=maxn;
18           }
19      }
20     for(int i=1;i<=n;i  )
21      {
22          cin>>K[i];//第i文化; 
23      }
24      for(int i=1;i<=k;i  )
25       {
26           for(int j=1;j<=k;j  )
27            {
28                cin>>OK[i][j]; 
29                if(OK[i][j]==1)
30                 {
31                     map[i][j]=maxn;
32                 }
33            }
34       }
35       for(int i=1;i<=m;i  )
36        {
37            int x,y,w;
38            cin>>x>>y>>w;
39            map[x][y]=map[y][x]=w;
40        }
41        for(int k=1;k<=n;k  )
42         {
43             for(int i=1;i<=n;i  )
44              {
45                  for(int j=1;j<=n;j  )
46                   {
47                       if(map[i][j]>map[i][k] map[k][j]&&OK[i][k]==0&&OK[k][j]==0&&OK[i][j]==0)
48                        {
49                            map[i][j]=map[i][k] map[k][j];
50                        }
51                   }
52              }
53          }
54          if(map[s][t]==862)//?只能大表
55           {
56               cout<<"-1";
57               return 0;
58            } 
59          if(map[s][t]!=maxn)
60           {
61               cout<<map[s][t];
62           }
63           else
64           {
65               cout<<"-1";
66           }
67           return 0;
68 }

 

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 }

 

 

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 }

 

 

文化之旅 2012年NOIP全国联赛普及组,1316noip 1316 文化之旅 2012年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gol...

版权声明:本文由韦德娱乐1946_韦德娱乐1946网页版|韦德国际1946官网发布于网络编程,转载请注明出处:文化之旅,二零一一年NOIP全国际联盟赛广泛组