擿埴索途
483 字
2 分钟
擿埴索途
题目描述
新生初入庠序,楼宇纵横,歧路交错。欲自“一”处达于“六”处,擿埴索途,步步试探。乃效古人结绳之计,逐一摸索,终得捷径:由一至二,达四,过五,抵六。不过四步,豁然开朗,遂寻得坦途。
给定一个包含 n 个顶点和 m 条边的无向图,顶点编号为 1, 2, …, n。每条边连接两个不同的顶点 u, v,表示这两个顶点之间存在一条双向道路。每经过一条边,距离增加 1。 现在给定起点 s 和终点 t,请你求出从 s 到 t 的最短距离,即从 s 到 t 所经过的最少边数。 如果无法从 s 到达 t,输出 -1。 注意:图中可能存在重边,也可能存在多个连通分量。
输入描述
第一行包含两个整数 n, m (1 <= n, m <= 2 * 10^5),分别表示顶点数和边数。
接下来 m 行,每行包含两个整数 u, v (1 <= u, v <= n),表示顶点 u 和顶点 v 之间存在一条双向道路。
最后一行包含两个整数 s, t (1 <= s, t <= n),分别表示起点和终点。
输出描述
输出一个整数,表示从 s 到 t 的最短距离。 如果终点无法到达,输出 -1。
示例1
输入
6 61 21 32 43 44 55 61 6输出
4说明
一条最短路径为 1 -> 2 -> 4 -> 5 -> 6,共经过 4 条边。
备注

我的代码
#include <bits/stdc++.h>using namespace std;int main (){ int n,m; cin>>n>>m; vector <vector <int>> g (n+1);
for (int i=0;i<m;i++) //邻接表 { int v; int u; cin>>v>>u; g[v].push_back(u); g[u].push_back(v); }
int s,t; cin>>s>>t;
vector<int> dist(n + 1, -1); //距离 queue<int> q; //队列
dist[s] = 0; //初始化 q.push(s);
while(!q.empty()) { int u; u=q.front(); q.pop(); for(int v:g[u]) { if(dist[v]!=-1) { continue; } dist[v]=dist[u]+1; q.push(v); } }
cout << dist[t] << '\n';}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




