NOIP2014D2T2寻找道路（Spfa）

洛谷传送门

这道题可以把边都反着存一遍，从终点开始深搜，然后把到不了的点 和它们所指向的点都去掉。

最后在剩余的点里跑一遍spfa就可以了。

——代码

#include <cstdio>

#include <cstring>

#include <queue>

const int maxn = ;

int n, m, s, t, cnt1, cnt2;

int dis[maxn];

int next1[ * maxn], to1[ * maxn], head1[ * maxn],

    next2[ * maxn], to2[ * maxn], head2[ * maxn];

bool vis[maxn], b[maxn], f[maxn], flag;

inline void add1(int x, int y)

{

    to1[cnt1] = y;

    next1[cnt1] = head1[x];

    head1[x] = cnt1++;

}

inline void add2(int x, int y)

{

    to2[cnt2] = y;

    next2[cnt2] = head2[x];

    head2[x] = cnt2++;

}

inline void dfs(int u)

{

    int i, v;

    if(u == s) flag = ;

    vis[u] = ;

    for(i = head2[u]; i != -; i = next2[i])

    {

        v = to2[i];

        if(!vis[v]) dfs(v);

    }

}

inline void spfa(int u)

{

    int i, j;

    std::queue <int> q;

    q.push(u);

    f[u] = ;

    dis[u] = ;

    while(!q.empty())

    {

        i = q.front();

        q.pop();

        f[i] = ;

        for(j = head1[i]; j != -; j = next1[j])

         if(!b[i] && !b[to1[j]] && dis[to1[j]] > dis[i] + )

         {

             dis[to1[j]] = dis[i] + ;

             if(!f[to1[j]])

             {

                 f[to1[j]] = ;

                 q.push(to1[j]);

             }

         }

    }

}

int main()

{

    int i, j, x, y;

    memset(head1, -, sizeof(head1));

    memset(head2, -, sizeof(head2));

    memset(dis,  / , sizeof(dis));

    scanf("%d %d", &n, &m);

    for(i = ; i <= m; i++)

    {

        scanf("%d %d", &x, &y);

        add1(x, y);

        add2(y, x);

    }

    scanf("%d %d", &s, &t);

    dfs(t);

    if(!flag)

    {

        printf("-1");

        return ;

    }

    for(i = ; i <= n; i++)

     if(!vis[i])

     {

         b[i] = ;

         for(j = head2[i]; j != -; j = next2[j]) b[to2[j]] = ;

     }

    spfa(s);

    printf("%d", dis[t]);

    return ;

}