题解 P2296 【寻找道路】

· · 题解

Problem

P2296 【寻找道路】

solution

首先声明，这题我用了spfa，而：

关于spfa：它死了。

杀手：NOI\ {2018}-T1出题人

感谢出题人，没有卡spfa

先说思路：

  1. 首先，要处理出哪些点不能直接或间接与终点连通
    • 函数：void live(void)
    • 这里的方法是建反图跑spfa
    • 不能直接或间接与终点连通的点存在temp_alive数组里，1为活着，0为死了
  2. 其次，要把所有指向不能直接或间接与终点连通的那些点的那些点设置为死了
    • 在函数live()里执行
    • 存到alive数组，1为活着，0为死了
    • 注意：第二步的结果不能直接直接存储在第一步的数组里，否则会杀掉一些有用的点
  3. 一遍spfa求最短路，求的过程中排除所有那些死了的点。
    • 函数：void spfa(void)
    • 注意路径长度均为1
  4. 完结散花♪(^∇^*)

Code

// luogu-judger-enable-o2
/*
    Problem: P2296 【寻找道路】 
    Author: 航空信奥 
    Date: 2018/08/16
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define Clear(a, x) memset(a, x, sizeof(a))
using namespace std;

namespace hkxa { /* 防重名 */
    inline char Getchar();
    template <typename _TpInt> inline _TpInt read();
    template <typename _TpInt> inline void write(_TpInt x);

#   define Max_N 10003

    vector<int> to[Max_N];
    vector<int> fr[Max_N]; /* 反图 */
    int n, m;
    int start, finish;
    bool alive[Max_N] = {0};
    int dis[Max_N] = {0};

    void live()
    {
        bool temp_alive[Max_N] = {0};
        queue <int> q;
        q.push(finish);
        temp_alive[finish] = 1;
        int point;
        while (!q.empty()) {
            point = q.front();
            q.pop();
            for (int i = 0; i < fr[point].size(); i++) {
                if (!temp_alive[fr[point][i]]) {
                    q.push(fr[point][i]);
                    temp_alive[fr[point][i]] = 1;
                }
            }
        }
        Clear(alive, 1);
        for (int i = 1; i <= n; i++) {
            if (!temp_alive[i]) {
                alive[i] = 0;
                for (int j = 0; j < fr[i].size(); j++) {
                    alive[fr[i][j]] = 0;
                }
            }
        }
    } 

    void spfa()
    {
        Clear(dis, 0x3f);
        dis[start] = 0;
        queue <int> q;
        q.push(start);
        int point;
        while (!q.empty()) {
            point = q.front();
            q.pop();
            for (int i = 0; i < to[point].size(); i++) {
                if (alive[to[point][i]] && dis[point] + 1 < dis[to[point][i]]) {
                    q.push(to[point][i]);
                    dis[to[point][i]] = dis[point] + 1;
                }
            }
        }
    } 

    int main() 
    {       
        n = read<int>();
        m = read<int>();
        int f, t;
        for (int i = 0; i < m; i++) {
            f = read<int>();
            t = read<int>();
            to[f].push_back(t);
            fr[t].push_back(f);
        }
        start = read<int>();
        finish = read<int>();

        live();
        spfa();
        if (dis[finish] == 0x3f3f3f3f)
            dis[finish] = -1;
        write(dis[finish]);
        puts("");

        return 0;
    }

    char BufferRead[1 << 15];
    int rLen = 0, rPos = 0;
    inline char Getchar()
    {
        if (rPos == rLen) rPos = 0, rLen = fread(BufferRead, 1, 1 << 15, stdin);
        if (rPos == rLen) return EOF;
        return BufferRead[rPos++];
    } 

    template <typename _TpInt>
    inline _TpInt read()       
    {
        register int flag = 1;
        register char c = Getchar();
        while ((c > '9' || c < '0') && c != '-') 
            c = Getchar();
        if (c == '-') flag = -1, c = Getchar();
        register _TpInt init = (c & 15);
        while ((c = Getchar()) <= '9' && c >= '0') 
            init = (init << 3) + (init << 1) + (c & 15);
        return init * flag;
    }

    template <typename _TpInt>
    inline void write(_TpInt x)
    {
        if (x < 0) {
            putchar('-');
            write<_TpInt>(~x + 1);
        }
        else {
            if (x > 9) write<_TpInt>(x / 10);   
            putchar(x % 10 + '0');
        }
    }
}

int main()
{
    hkxa::main();
    return 0;
}