首页 > 试题广场 >

【模板】单源最短路1

[编程题]【模板】单源最短路1
  • 热度指数：11261 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你一个无向图，图中包含 5000 个点 m 个边，任意两个点之间的距离是 1 ，无重边或自环。请求出1号点到n号点的最短距离。

注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.

输入描述:
第一行两个整数n和m，表示图的点和边数。
接下来m行，每行两个整数u，v，表示u到v有一条无向边。



输出描述:
输出一行，表示1到n的最短路，如不存在，输出-1.
示例1

输入

4 4
1 2
2 4
3 4
3 1

输出

2
示例2

输入

4 3
1 2
2 3
3 1

输出

-1

说明

1号点不能到4号点。
算法知识视频讲解
开通博客
头像 Coming680
发表于 2022-05-06 21:51:30
#include<iostream> #include<queue> #include<map> #include<vector> #include<algorithm> using namespace std; map< 展开全文
去ta的博客 赞 (7) 回复(1) 收起
头像 KEY.L
发表于 2022-07-06 22:02:02
注意看题目的数据范围！！！！！！！！！ 不难发现这是一个稀疏图 而堆优化版dijkstra适合稀疏图 那还想什么，直接堆优化上就完事了 不过我使用的是优先队列，没有手写堆~~~~~ #include<bits/stdc++.h> using nam 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 牛客338107602号
发表于 2022-07-01 23:46:32
总结：1.java中boolean默认为flase,对象默认为null2.无权图计算单源最短路径可以使用广度优先算法，借助队列记忆将要访问的下一层顶点。可以使用visited[]标志顶点是否被访问过，以防止被多次访问。 import java.util.*; public class Main{ 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 lirich674
发表于 2022-08-17 19:18:42
广度优先搜索 每往下搜索一层，步数加一。如果最后没搜索到，return -1； #include<bits/stdc++.h> using namespace std; int sol(vector<vector<int>>mp,int len){ 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 蚂蚁go
发表于 2024-03-14 15:09:43
#include <bits/stdc++.h> using namespace std; const int MAX=5010; vector<int> a[MAX];//存储无向边 bool mark[5010];//标记边是否已被遍历 int bfs(int b,int 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 强大的羚羊说这不是bug
发表于 2025-04-06 16:22:26
邻接表与邻接矩阵空间复杂度直观差异邻接表 空间复杂度 O(N+M) 邻接矩阵 空间复杂度O(N*N) //邻接表 #include <bits/stdc++.h> using namespace std; const int N = 5001; int bfs(int n, vec 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客588161781号
发表于 2023-12-08 11:20:33
//Dijkstra #include <iostream> #include <queue> #include<vector> #include<algorithm> #include<cstring> using namespace s 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客588161781号
发表于 2023-12-08 11:20:46
//Dijkstra #include <iostream> #include <queue> #include<vector> #include<algorithm> #include<cstring> using namespace s 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客510028288号
发表于 2023-04-10 17:18:49
#include <climits> #include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n = 0, m 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 陪我吹吹海风吧
发表于 2024-05-03 20:21:08
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_NODES 5009 // 定义邻接表节点 typedef struct Node { int vertex; 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

难度：
26条回答 627浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】单源最短路1

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号