翻车笔记_ Noip2014Day2T2 [BFS]

图论都好说

懵逼的 题目

传送至 Luogu

扯淡的 题解

这道题看完就爆正解了…然后写完就gg了…
首先是路径上的所有点的出边所指向的点都直接或间接与终点连通。应该把所有终点不能直接到达的点的前一个点删掉…窝却把它到起点的整条路径都删了(国文太差.jpg)…
然后改完了过了2个点…
调了半天发现v数组没有初始化…喜欢定义全局变量的窝似乎忘了还要初始化呢…
最后…代码好丑啊…码力好差啊…

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <queue>
#define INF (0x7fffffff)
#define MAXN (10000 + 5)
#define MAXM (200000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct bf
{
int node;
int cost;
}a[MAXN];
struct edg
{
int from;
int to;
int next;
}b[MAXM], c[MAXM];
//bool vis[MAXN];
int precan[MAXN];
int ans = INF;
int gc[MAXN];
int gb[MAXN];
int cnte = 0;
int n;
int m;
int s, t;
int d[MAXN];
bool can[MAXN];
bool canb[MAXN];
void adn(int, int);
void bfs(int);
void init();
void bfs2(int);
void inbfs(int);
int main()
{
memset(can, false, sizeof(can));
memset(canb, true, sizeof(canb));
scanf("%d%d", &n, &m);
int srx, sry;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
}
scanf("%d%d", &s, &t);
bfs(t);
init();
bfs2(s);
if (ans != INF)
printf("%d", ans);
else
puts("-1");
return 0;
}
void adn(int fr, int to)
{
b[++cnte].from = fr; c[cnte].from = to;
b[cnte].to = to; c[cnte].to = fr;
b[cnte].next = gb[fr]; c[cnte].next = gc[to];
gb[fr] = cnte; gc[to] = cnte;
}
void bfs(int startDash)
{
bool v[MAXN];
memset(v, false, sizeof(v));
queue<int> q;
q.push(startDash);
int dq;
while (!q.empty())
{
dq = q.front(); q.pop();
v[dq] = true;
can[dq] = true;
for (int i = gc[dq]; i; i = c[i].next)
{
if (!v[c[i].to])
q.push(c[i].to);
}
}
}
void bfs2(int startDash)
{
bool v[MAXN];
memset(v, false, sizeof(v));
queue<bf> q;
q.push({startDash, 0});
bf dq;
while (!q.empty())
{
dq = q.front(); q.pop();
v[dq.node] = true;
if (dq.node == t)
{
ans = dq.cost;
break;
}
for (int i = gb[dq.node]; i; i = b[i].next)
{
if (canb[b[i].to] && (!v[b[i].to]))
{
q.push({b[i].to, dq.cost + 1});
}
}
}
}
void init()
{
for (int i = 1; i <= n; i++)
{
for (int j = gb[i]; j; j = b[j].next)
{
if (!can[b[j].to])
{
canb[i] = false;
break;
}
}
}
}
/*void inbfs(int startDash)
{
queue<int> q;
q.push(startDash);
int dq;
while(!q.empty())
{
dq = q.front(); q.pop();
vis[dq] = true;
can[dq] = false;
for (int i = gc[dq]; i; i = c[i].next)
{
if (!vis[c[i].to])
{
q.push(c[i].to);
}
}
}
}*/
/*
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
*/

By 被beat的 Cansult