AcWing 847. 图中点的层次 C++
原题链接
简单
作者:
LaChimere
,
2021-05-25 16:36:05
,
所有人可见
,
阅读 247
C++
#include <iostream>
#include <unordered_set>
#include <queue>
using namespace std;
const int MAXSIZE = 100010;
int n, m;
vector<unordered_set<int> > graph(MAXSIZE, unordered_set<int>());
vector<bool> visited(MAXSIZE, false);
vector<unsigned> dist(MAXSIZE, -1);
queue<int> q;
int bfs() {
dist[1] = 0;
q.push(1);
while (!q.empty()) {
int v = q.front();
q.pop();
if (visited[v]) {
continue;
}
visited[v] = true;
if (v == n) {
break;
}
for (int u : graph[v]) {
dist[u] = min(dist[u], dist[v]+1);
q.push(u);
}
}
return dist[n];
}
void addEdge(int v, int u) {
graph[v].insert(u);
}
void init() {
cin >> n >> m;
int a, b;
while (m--) {
cin >> a >> b;
if (a != b) {
addEdge(a, b);
}
}
}
int main() {
init();
cout << bfs() << endl;
return 0;
}