luoguP2296 寻找道路-LMLPHP

因为是出边与终点直接或间接相连,所以将边反向,从终边开始,将所有终边能到达的点都打上标记
因为是最短路,所以不需要处理重边和自环,于是再跑最短路就好
题目关键:
路径上的所有点的出边所指向的点都直接或间接与终点连通

这句话的意识也就是变相的告诉我们,对于一个点x, 他的一条出边连的点y并不能直接或间接的与终点相连,此时我们要给x打上标记
因此,我们在最初从终点开始扫的仅仅是终点能到达的,对于终点不能到达的,我们最后要单独把他们的父节点(方便理解的说法)安排上
但是如果只使用一个标记数组,会出现后效性,所以我们要使用两个标记数组

处理完后跑最短路即可

此题学会的操作:在特定时候,为了简化问题,可以将边反向

此题踩到的雷:kill是关键词,然后吃了两发ce(本来可以1A)

 #include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
const int maxm = ;
const int maxn = ;
struct shiki {
int y, net;
}e[maxm];
int lin[maxm], len = ;
int n, m, flag;
int s, t;
bool kil[maxn], vis[maxn];
int dis[maxn]; inline int read() {
int x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y = -;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} inline void insert(int xx, int yy) {
e[++len].net = lin[xx];
e[len].y = yy;
lin[xx] = len;
} void find_your_brother(int t) {
vis[t] = kil[t] = ;
for(int i = lin[t]; i; i = e[i].net)
if(!vis[e[i].y]) find_your_brother(e[i].y);
} queue<int> q;
inline void spfa(int st) {
memset(vis, , sizeof(vis));
memset(dis, 0x3f3f3f, sizeof(dis));
flag = dis[];
q.push(st); vis[st] = , dis[st] = ;
while(!q.empty()) {
int k = q.front(); q.pop();
vis[k] = ;
for(int i = lin[k]; i; i = e[i].net) {
int to = e[i].y;
if(!kil[to]) continue;
if(dis[to] > dis[k] + ) {
dis[to] = dis[k] + ;
if(!vis[to]) {
vis[to] = ;
q.push(to);
}
}
}
}
} int main() {
n = read(), m = read();
for(int i = ; i <= m; ++i) {
int x, y;
x = read(), y = read();
insert(y, x);//反向建边
}
s = read(), t = read();
find_your_brother(t);
for(register uint i = ; i <= n; ++i) {
if(!vis[i])
for(int j = lin[i]; j; j = e[j].net)
if(kil[e[j].y]) kil[e[j].y] = ;
}
spfa(t);
if(dis[s] >= flag) cout << - << '\n';
else cout << dis[s] << '\n';
return ;
}
05-28 16:53