题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环。
所有边的长度都是1,点的编号为1~n。
请你求出1号点到n号点的最短距离,如果从1号点无法走到n号点,输出-1。
输入格式
第一行包含两个整数n和m。
接下来m行,每行包含两个整数a和b,表示存在一条从a走到b的长度为1的边。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
数据范围
1≤n,m≤105
输入样例:
4 5
1 2
2 3
3 4
1 3
1 4
输出样例:
1
思路
由于遍历的方式是按照层来进行遍历的,每次记录同一层中满足条件的所有元素,标记好元素的个数,并将每个元素的距离置为当前层数 - 1
java
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int N = 100010;
static int n, m; // n点 m边
static int[] h = new int[N], e = new int[N], ne = new int[N];
static int idx;
static int[] d = new int[N];
static Queue<Integer> queue = new LinkedList<>();
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
//只是遍历,没有回溯,不需要考虑恢复现场
private static int bfs() {
queue.offer(1);
int dist = 1;
int levelSize = 1;
d[1] = 0;
while(!queue.isEmpty()) {
int t = queue.poll();
levelSize --;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = dist;
queue.offer(j);
}
}
if (levelSize == 0) {
levelSize = queue.size();
dist ++;
}
}
return d[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
h[i] = -1;
d[i] = -1;
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
}
System.out.println(bfs());
}
}
python
N = 100010
h, e, ne = [-1] * N, [0] * N, [0] * N
d = [-1] * N
n, m, idx = 0, 0, 0
def add(a, b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def bfs():
queue = [1]
dist = 1
levelSize = 1
d[1] = 0
while queue:
t = queue.pop(0)
levelSize -= 1
i = h[t]
while i != -1:
j = e[i]
if d[j] == -1:
d[j] = dist
queue.append(j)
i = ne[i]
if levelSize == 0:
levelSize = len(queue)
dist += 1
return d[n]
def main():
global n, m
n, m = map(int, input().split())
for i in range(m):
a, b = map(int, input().split())
add(a, b)
print(bfs())
if __name__ == '__main__':
main()
c++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
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 ++;
}
int bfs(){
int hh = 0, tt = 0;
int levelSize = 1; //记录每一层的节点数量
int dist = 1; //距离
q[0] = 1;
memset(d, -1, sizeof d);
d[1] = 0;
while(hh <= tt){
int t = q[hh ++];
levelSize --;
//记录当前节点下所有未被访问过的邻接点
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(d[j] == -1){ //未访问过的点,加入到队列
d[j] = dist;
q[++ tt] = j;
}
}
if(levelSize == 0){
levelSize = tt - hh + 1;
dist ++ ;
}
}
return d[n];
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++){
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
}