[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