AcWing 847. 图中点的层次(配合python代码理解)    原题链接    简单

作者： 作者的头像   simonhan ,  2021-03-26 10:43:41 ,  所有人可见 ,  阅读 374

0


其实这道题最好辅助理解的代码应该使用python写的

可以分为三个步骤，读数据，构建邻接表，之后配一个宽搜的模板。因为python的list有可以当栈有可以当list还可以构建邻接表。所以极度方便。

if __name__=="__main__":
    n,m = map(int,input().split())
    #h是我要构建的邻接表
    h = [[] for _ in range(n + 10)] 
    #distance
    d = [-1] * (n + 10)
    #宽搜队列
    q = []

    def add(a,b):
        h[a].append(b)
    #宽搜模板
    def bfs(q,n):
        q.append(1)
        d[1] = 0
        while q:
            t = q[0]
            q = q[1:]
            for node in h[t]:
                if(d[node] == -1):
                    d[node] = d[t] + 1
                    q.append(node)
        return d[n]

    for i in range(m):
        a,b = map(int,input().split())
        add(a,b)

    print(bfs(q,n))

C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];

//构建邻接表
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

//bfs返回最短路长度
int bfs(){
    int hh = 0,tt = 0;
    q[0] = 1;
    memset(d,-1,sizeof d);
    d[1] = 0;
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];

}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    cout << bfs() << endl;
    return 0;
}

1 评论

用户头像
很遗憾   2021-03-26 11:57         踩      回复 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int N = 100010;
    static int h[] = new int[N];
    static int e[] = new int[N];
    static int ne[] = new int[N];
    static int idx = 0;
    static int n,m;
    static int max = 0x3f3f3f;

    static int []d = new int[N];
    static int []q = new int[N];
    public static void add(int a, int b){
        e[idx] = b;ne[idx] = h[a];h[a] = idx++;
    }
    public static void bfs(){
        int hh = 0, tt = -1;
        Arrays.fill(d,max);
        d[1] = 0;
        q[++tt] = 1;

        while(hh <= tt){
            int t = q[hh++];
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(d[j] == max) {
                    d[j] =  d[t] + 1;
                    q[++tt] = j;
                }
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String []s = in.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        Arrays.fill(h,-1);
        while (m -- != 0){
            String []s1 = in.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            int b = Integer.parseInt(s1[1]);
            add(a,b);
        }
        bfs();
        if(d[n] == max) System.out.println(-1);
        else
            System.out.println(d[n]);

    }
}