题目描述
给定一个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
BFS
解答
看似图问题 其实是一个走迷宫问题 使用BFS天然可以得到最短路径
那么根据输入数据得到那两点之间有关联 从点1开始进行BFS。
这里做了一点小改动 vis本来是01只代表是否该点被访问过 这里改为 0 表示该点未访问
其余数字表示点1到达该点的距离
C++ 代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<vector<int>> graph(100010, vector<int>());
int vis[100010];
queue<int> q;
void solve()
{
q.push(1);
while (!q.empty()) {
int ele = q.front();
q.pop();
int distance = vis[ele];
for (int i = 0; i < graph[ele].size(); i++) {
int next = graph[ele][i];
if (next == n) {
cout << distance + 1 << endl;
return;
}
if (vis[next] == 0) {
//该点没被访问
vis[next] = distance + 1;
q.push(next);
}
}
}
cout << -1 << endl;
return;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
}
solve();
return 0;
}