图论都好说

懵逼的 题目

传送至 Luogu

扯淡的 题解

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

沙茶的 代码

#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