Description
Solutions
考虑使用 SPFA 来解题。
先整理出题意中包含的条件：
| 1 |
有 n 个点， m 条边（输入输出里面写了），q 个询问。 |
| 2 |
每一次询问中，会给 a_i 号点一个值 L 。 |
| 3 |
i 号点如果有一个值 L 且 L > 0，那么与它有边连接的点就都会有一个值 L-1 ，当 L=0 时，这个点就会被标记。 |
| 4 |
若 1 号点会被标记时，此询问就要输出 “Yes” ，否则输出 “No” 。 |
因为走到一号点有走了单数条边和双数条边两种情况，那么我们设 $ma_i$ 和 $mb_i$ 分别表示 $i$ 号点到 1 号点的走单数条边和走双数条边的最短路径长度，用 $SPFA$ 去求这些数（剪个枝，时间复杂度不高）。
然后对于每组提问，我们只需要先判断一下这个走的步数 $L$ ：如果是单数，就与 $ma_i$ 比一下，如果小于 $ma_i$ ，那就肯定走不到，如果大于等于 $ma_i$ ，那就能走到。复数的话同理比较。
然后这道题就做完了，详见 代码 部分。
Code
1 | #include<cmath>
|
2 | #include<cstdio>
|
3 | #include<cstring>
|
4 | #include<iostream>
|
5 | #include<algorithm>
|
6 | using namespace std;
|
7 | const int tp=1000000;
|
8 | int n,m,q,len,tou,wei,an;
|
9 | int last[100001],ma[100001],mb[100001];
|
10 | struct nod{int to,next;}d[200001];
|
11 | struct node{int x,s;}f[1000000];
|
12 | bool bz[100001];
|
13 | void jianbian(int x,int y)
|
14 | {
|
15 | d[++len].to=y;
|
16 | d[len].next=last[x];
|
17 | last[x]=len;
|
18 | }
|
19 | void bfs(int a)
|
20 | {
|
21 | tou=0,wei=1;
|
22 | f[tou].x=a;f[tou].s=0;
|
23 | while(tou!=wei)
|
24 | {
|
25 | for(int i=last[f[tou].x];i!=0;i=d[i].next)
|
26 | {
|
27 | if(f[tou].s%2==1)
|
28 | {
|
29 | if(mb[d[i].to]>f[tou].s+1)
|
30 | {
|
31 | mb[d[i].to]=f[tou].s+1;
|
32 | f[wei].x=d[i].to;
|
33 | f[wei].s=f[tou].s+1;
|
34 | wei=(wei+1)%tp;
|
35 | }
|
36 | }
|
37 | else
|
38 | {
|
39 | if(ma[d[i].to]>f[tou].s+1)
|
40 | {
|
41 | ma[d[i].to]=f[tou].s+1;
|
42 | f[wei].x=d[i].to;
|
43 | f[wei].s=f[tou].s+1;
|
44 | wei=(wei+1)%tp;
|
45 | }
|
46 | }
|
47 | }
|
48 | tou=(tou+1)%tp;
|
49 | }
|
50 | }
|
51 | int main()
|
52 | {
|
53 | freopen("work.in","r",stdin);
|
54 | freopen("work.out","w",stdout);
|
55 | memset(ma,127/3,sizeof(ma));
|
56 | memset(mb,127/3,sizeof(mb));
|
57 | scanf("%d%d%d",&n,&m,&q);
|
58 | for(int i=1;i<=m;i++)
|
59 | {
|
60 | int u,v;
|
61 | scanf("%d%d",&u,&v);
|
62 | jianbian(u,v);
|
63 | jianbian(v,u);
|
64 | }
|
65 | bfs(1);
|
66 | for(int i=1;i<=q;i++)
|
67 | {
|
68 | int a,l;
|
69 | scanf("%d%d",&a,&l);
|
70 | if(ma[a]>700000000&&mb[a]>700000000)
|
71 | {
|
72 | printf("No\n");
|
73 | }
|
74 | else if(l%2==1)
|
75 | {
|
76 | if(ma[a]<=l)
|
77 | {
|
78 | printf("Yes\n");
|
79 | }
|
80 | else
|
81 | {
|
82 | printf("No\n");
|
83 | }
|
84 | }
|
85 | else
|
86 | {
|
87 | if(mb[a]<=l)
|
88 | {
|
89 | printf("Yes\n");
|
90 | }
|
91 | else
|
92 | {
|
93 | printf("No\n");
|
94 | }
|
95 | }
|
96 | }
|
97 | return 0;
|
98 | }
|
