难点叙述 Description,则他就不可以到达其他有那种知识的国家)

1316 文化之旅

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

时间限制: 1 s

空间范围: 128000 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 }

 

 

时刻限定: 1 s

 空间范围: 128000
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

 

样例输出 萨姆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;

对于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。

 

数据最大100 -> floyd

屠龙宝刀点击就送

#include <ctype.h>
#include <cstdio>
#define N 1005
void read(int &x)
{
    x=0;
    register char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
}
int min(int a,int b) {return a>b?b:a;} 
int Map[N<<1][N<<1],c[N<<1],n,k,m,s,t,pc[N][N];
int main()
{
    read(n);read(k);read(m);read(s);read(t);
    for(int i=1;i<=n;i++) read(c[i]);
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            read(pc[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            Map[i][j]=0x7ffffff; 
    for(int x,y,z;m--;)
    {
        read(x);
        read(y);
        read(z);
        if(!pc[c[y]][c[x]]) Map[x][y]=min(Map[x][y],z);
        if(!pc[c[x]][c[y]]) Map[y][x]=min(Map[y][x],z);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                if(!pc[c[j]][c[k]]&&!pc[c[j]][c[i]]&&!pc[c[i]][c[k]])
                Map[j][k]=min(Map[j][k],Map[j][i]+Map[i][k]);
            }
        }
    }
    if(Map[s][t]>=0x7ffffff) printf("-1");
    else printf("%d",Map[s][t]);
    return 0;
}

 

相关文章

网站地图xml地图