地址 https://www.acwing.com/problem/content/849/
给定一个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
解答
看似图问题 其实是一个走迷宫问题 使用BFS天然可以得到最短路径
那么根据输入数据得到那两点之间有关联 从点1开始进行BFS。
这里做了一点小改动 vis本来是01只代表是否该点被访问过 这里改为 0 表示该点未访问 其余数字表示点1到达该点的距离
#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; }