本文共 1705 字，大约阅读时间需要 5 分钟。

知识点：广度搜索+存储距离（每移动一层就将当前层的距离设置为上层+1）

给定一个n个点m条边的有向图，图中可能存在重边和自环。

所有边的长度都是1，点的编号为1~n。

请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

4 51 22 33 41 31 4

输出样例：

1

import java.io.*;import java.lang.*;import java.util.*;class Main{    static int N = 100010;    static int[] q = new int[N];//队列    static int[] d = new int[N];//存储节点之间最短距离    static int[] h = new int[N], e = new int[N], ne = new int[N];//存储邻接表    static int idx = 1;//节点编号从1开始的我们这也设置为1    static int n = 0;    static void add(int k, int n){//节点插入邻接表        e[idx] = n; ne[idx] = h[k]; h[k] = idx++;    }    static int bfs(){        int hh = 0, tt = 0;//队头队尾指针        Arrays.fill(d, -1);//距离初始化为-1        d[1] = 0;        q[0] = 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] == -1){//如果当前节点没有搜索过                    d[j] = d[t] + 1;                    q[++tt] = j;//存储邻接表数组下标                }            }        }        return d[n];    }    public static void main(String[] args)throws Exception{        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));        String[] params = buf.readLine().split(" ");        n = Integer.valueOf(params[0]);        int m = Integer.valueOf(params[1]);        Arrays.fill(h, -1);//将邻接表数组初始化为-1        for(int i = 1; i <= m; ++i){            String[] info = buf.readLine().split(" ");            int k = Integer.valueOf(info[0]);            int c = Integer.valueOf(info[1]);            add(k, c);//构建邻接表        }        System.out.print(bfs());    }}

转载地址：http://nure.baihongyu.com/