网页设计与制作期末考试试题及答案_中企动力骗子公司_公司网络推广排名定制_湖北搜索引擎优化

题面

对于给定的有向图 G = (V, E)，编写一个程序来找出从顶点 1 到每个顶点的最短距离 d（路径上的最小边数）。每个顶点从 1 到 n 编号。 对于不能从顶点 1 到达的顶点，输出 -1。

输入

第一行给出了 G 中的顶点数 n。 接下来的 n 行给出了每个顶点 u 的邻接表，格式如下：

ukv1​v2​…vk​

u 是顶点的编号，k 是 u 的度数，v1​v2​…vk​是与 u 相邻的顶点的编号。

约束
1≤n≤100

输出

在一行上输出每个顶点的 id 和 d。 id 是顶点的编号，d 是顶点 1 到该顶点的距离。 按顶点编号顺序输出。

输入样例

4
1 2 2 4
2 1 4
3 0
4 1 3

输出样例

1 0
2 1
3 2
4 1 

代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> using namespace std;// BFS函数，接受图的邻接表和起始节点
void bfs(int start, const vector<vector<int>>& adj, vector<int>& visited,int n) {queue<int> q;q.push(start);visited[start] = 0;while (!q.empty()) {int u = q.front();q.pop();for (int v : adj[u]) {if (visited[v]==-1) {visited[v] = visited[u]+1;q.push(v);}}}cout << endl;  
}int main() {int n;cin >> n;vector<vector<int>> adj(n);vector<int> visited(n, -1);for (int i = 0; i < n; ++i) {int u, k;cin >> u >> k;u--;for (int j = 0; j < k; ++j) {int v;cin >> v;v--;adj[u].push_back(v);}}bfs(0,adj,visited,n);for(int i=0;i<n;i++){cout <<(i+1)<<" "<<visited[i]<<endl;}return 0;
}