首页 > 试题广场 >

最短路径

[编程题]最短路径
  • 热度指数：19642 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离

输入描述:
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路
接下来M行两个整数，表示相连的两个城市的编号


输出描述:
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
示例1

输入

4 4
1 2
2 3
1 3
0 1

输出

8
9
11
算法知识视频讲解
开通博客
头像 flyflyfly00
发表于 2021-04-20 21:53:09
这样写答案不对 #include <iostream> using namespace std; const int mod = 100000; const int INF = 100000000; const int N = 100; int n, m; int path[N][ 展开全文
去ta的博客 赞 (12) 回复(0) 收起
头像 Tshaxz
发表于 2023-04-11 12:17:32
方法一：弗洛伊德+并查集 #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 110, MOD = 100000, INF 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 牛客419094931号
发表于 2022-03-05 16:55:56
借鉴了讨论区大佬的最小生成树思路：第n条边的长度比前面所有n-1条边的长度之和还要大，最短路径一定走的是最小生成树 所以遍历第0到第m-1条边，只保存最小生成树的边，其他的扔掉 同时最小生成树内的最短路径都是唯一的，所以边的长度可以直接取模 最后通过DFS计算出0结点到其余节点的路径长度 #incl 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 TheOnlyMan
发表于 2021-02-24 17:17:37
很明显，n最大100，floyd算法可以胜任o(Cn^3)复杂度,c是高精度的系数。当然用堆优化的迪克特斯拉或者spfa都可以秒了此题。显然我懒（不是）。​具体用到有高精+高精，高精*单精，高精比较高精； ​#include<iostream> #include<cstdio> 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 程昱同学
发表于 2023-01-25 19:41:48
#include<iostream> #include<string> using namespace std; //本题坑点：会重复输入边，本题以第一次输入为准，切忌覆盖 //方法：高精度运算和弗洛伊德 //注意：是无向图 //高精度乘法 //999999999999999 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客375632021号
发表于 2024-02-18 14:56:04
//先用Dijkstra硬写了一遍 #include <cstdlib> #include <cstring> #include <iostream> #include <typeindex> #include <vector> #incl 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 鱼儿恋上水
发表于 2020-04-23 21:59:33
①弗洛伊德算法 #include <bits/stdc++.h> using namespace std; int n, m;//n城市个数、m道路数 const int MAXV = 105; //大数结构体 struct bign{ int d[150], len; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 电专小胖墩
发表于 2024-02-08 21:30:06
从Prim算法和Dijkstra算法两种算法异同的角度说明为何本题最小生成树中包含了所有最短路径。两种思路：最短路+高精度加乘（最容易想到的方法，该题大数可以用二进制数组表示比较方便）最小生成树+dfs这里着重记录第二种思路。首先说明一下为什么最小生成树中包含了所有最短路径。这里不得不提及一下Pri 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 SStarry
发表于 2023-08-25 10:25:58
#include <iostream> using namespace std; const int N = 110; const int INF = 0x3f3f3f3f; const int MOD = 100000; int n, m; int path[N][N]; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 吴明示
发表于 2022-03-13 14:55:27
Dijkstra算法的暴力修正，用“相对距离”来替代“绝对距离” #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cl 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 图 并查集
难度：
64条回答 15165浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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