视频加载失败

擿埴索途

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 6
1 2
1 3
2 4
3 4
4 5
5 6
1 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';
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

擿埴索途
https://www.xiaobaibai454.top/posts/study-26-10-29/
作者
Xiao_baibai
发布于
2026-10-29
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录