[1537] Travel
时间限制: 2000 ms 内存限制: 65535 K
问题描述
One time, group master organized nekoTeam to travel, he always send a person to toilet before arriving a scene, and the rest of the people continued to move forward.
The scenes are numbered from 1 to n, nekoTeam was going from scene 1 to scene n.
输入
The first line contains an integer T, indicate the number of test cases.
The first line of each test case contains four integer: n m a b, separated by spaces (1 <= n, a, b <= 40), represents the number of scenes, paths, boys, girls.
The second line is string consists of n characters, the i-th character indicate the toilet type of the i-th scene, 'A' for men's room, 'B' for women's room.
The next m lines each contains two positive integers u v, indicate there is a two-way path between scene u and scene v. There is no multiple-paths and self-paths
输出
For each test case, if anyone can go to senario n, output 'yes', otherwise 'no'.
样例输入
3
3 2 2 1
AAB
1 2
2 3
3 2 1 2
AAB
1 2
2 3
2 1 1 1
AA
1 2
样例输出
yes
no
no
题意和思路：n，m，a，b分别代表场景数，道路数，男孩数量和女孩数量，下面是一个有n个字符的字符串str，'A'代表男洗手间，'B'代表女洗手间。下面的m行是路径，问按照题目所给的走的标准走，能不能从1走到n。
把左右的路径标记到一个邻接矩阵里面，有路径的标为1，没有的就为0，利用广搜，把结果更新到dist数组里面，最后看看dist得到的值能不能满足str所给的顺序。dist里面始终存小的值。具体如下：
1 /*
2 ID: asif
3 LANG: C++
4 TASK: test
5 */
6 //# pragma comment(linker, '/STACK:102400000,102400000')
7 # include<iostream>
8 # include<cstdio>
9 # include<cstdlib>
10 # include<cstring>
11 # include<algorithm>
12 # include<cctype>
13 # include<cmath>
14 # include<string>
15 # include<set>
16 # include<map>
17 # include<stack>
18 # include<queue>
19 # include<vector>
20 # include<numeric>
21 using namespace std;
22 const int maxn=44;
23 const double inf=0.000001;
24 const int INF=~0U>>1;
25 const int mod=1000000007;
26 # define lson l,m,rt<<1
27 # define rson m+1,r,rt<<1 | 1
28 # define PS printf('
')
29 # define S(n) scanf('%d',&n)
30 # define P(n) printf('%d
',n)
31 # define Ps(n) printf(' %d',(n))
32 # define SB(n) scanf('%lld',&n)
33 # define PB(n) printf('%lld
',n)
34 # define PBs(n) printf(' %lld',n)
35 # define SD(n) scanf('%lf',&n)
36 # define PD(n) printf('%.3lf
',n)
37 # define Sstr(s) scanf('%s',s)
38 # define Pstr(s) printf('%s
',s)
39 # define S0(a) memset(a,0,sizeof(a))
40 # define S1(a) memset(a,-1,sizeof(a))
41 typedef long long ll;
42 int n,m,a,b,edge[maxn][maxn],dist[maxn][maxn][2],flag;
43 char str[maxn];
44 struct node
45 {
46 int x;
47 int y;
48 int suma;
49 int sumb;
50 };
51 void bfs()
52 {
53 node s,t;
54 s.x=0;
55 s.y=0;
56 if(str[0]=='A')
57 {
58 s.suma=1,s.sumb=0;
59 for(int i=0;i<n;i++)
60 if(edge[i][0])
61 dist[i][0][0]=1,dist[i][0][1]=0;
62 }
63 else
64 {
65 s.suma=0,s.sumb=1;
66 for(int i=0;i<n;i++)
67 if(edge[i][0])
68 dist[i][0][1]=1,dist[i][0][0]=0;
69 }
70 queue<node>q;
71 q.push(s);
72 while(!q.empty())
73 {
74 t=q.front();
75 q.pop();
76 for(int i=0;i<n;i++)
77 {
78 if(edge[t.x][i])
79 {
80 s.x=i;
81 if(str[i]=='A')
82 s.suma=t.suma+1,s.sumb=t.sumb;
83 else
84 s.suma=t.suma,s.sumb=t.sumb+1;
85 if(s.suma<dist[t.x][s.x][0]||s.sumb<dist[t.x][s.x][1])//确保是没有查询过的点，不加会超时
86 {
87 dist[t.x][s.x][0]=min(dist[t.x][s.x][0],s.suma);
88 dist[t.x][s.x][1]=min(dist[t.x][s.x][1],s.sumb);
89 if(s.x==n-1)
90 {
91 if(a>=s.suma&&b>=s.sumb)//找到符合条件的就退出
92 {
93 flag=1;
94 return;
95 }
96 }
97 q.push(s);
98 }
99 }
100 }
101 }
102 }
103 int main()
104 {
105 //freopen('input.in', 'r', stdin);
106 //freopen('output.out', 'w', stdout);
107 int T;
108 S(T);
109 while(T--)
110 {
111 scanf('%d%d%d%d',&n,&m,&a,&b);
112 S0(edge);
113 for(int i=0;i<maxn;i++)
114 for(int j=0;j<maxn;j++)
115 dist[i][j][0]=dist[i][j][1]=INF;
116 Sstr(str);
117 for(int i=0;i<m;i++)
118 {
119 int u,v;
120 S(u),S(v);
121 u--,v--;
122 edge[u][v]=edge[v][u]=1;
123 }
124 flag=0;
125 bfs();
126 if(flag)
127 puts('yes');
128 else
129 puts('no');
130 }
131 return 0;
132 }
View Code