Ideal Path（UVA - 1599）

最新推荐文章于 2022-10-04 10:38:10 发布
最新推荐文章于 2022-10-04 10:38:10 发布
阅读量300 收藏
点赞数
分类专栏： C++ 文章标签： 数据结构 算法 c++
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/zjsru_Beginner/article/details/125953530
版权

作者：Alex_Dawn

题目描述

给定一个nn个点mm条边的无向图，每条边上都涂有1种颜色。求点11到点nn的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接11和nn的道路。

输入输出样例

输入

4 6

1 2 1

1 3 2

3 4 3

2 3 1

2 4 4

3 1

最低0.47元/天 解锁文章
Ideal Path（UVA-1599）
子夜的博客
10-07 232
题目 推荐 题意 给定一个n个顶点，m条边的无向图，每条边有颜色值（长度均为1），求出起点到终点的最短路径（颜色值表示），若存在多解，则输出路径中颜色值字典序最小者。（注意重边，自环） 思路 逆向BFS求最短路径，正向BFS求字典序最小 代码如下 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; const int inf=0x3f3f3f3f; typedef long long ll; vector<i
UVA1599 理想路径 Ideal Path
m0_73035684的博客
11-03 174
上一个BFS蓝题练习了方向处理，地图的状态处理，输出任意一条最短路，这个题练习了不一样的东西，是输出一条有第二标尺的最短路，那么原先记录任意最短路径的方法就不适用，这里采用了两个BFS的写法，之所以这么写，是利用了BFS的队列里面的状态是关于层次具有两段性的这么一个性质，首先第一个广搜我们用来找最短路路径的长度，做好标记，并且是反向搜索，从终点到起点，为什么要这样，应该是为了能把所有的最短路径给包含进来，为了下一个找路径。
1599 - Ideal Path
zju2016的博客
07-28 262
紫书上面已经给出了很好的思路，首先从终点开始进行BFS，同时记录从终点开始到每个节点的最短路径的长度，这样一直到起点，然后从起点开始进行新的一轮的BFS，在新的一轮的BFS中，我们要记录所走路径的颜色信息，每次选择颜色最小的那一条路来走，同时要注意，如果从当前的节点开始有多条颜色最小的路径，那么我们要将相应节点的编号都要存到队列当中，在下一轮的时候依次出队列分别进行下一轮的比较，保证所走的路径的颜
UVA ~ 1599 ~ Ideal Path （非简单图 + 逆向BFS）
张松超的博客
05-20 483
题意：给一个n个点m条边（2≤n≤100000,1≤m≤200000）的无向图，每条边上都涂有一种颜色。求从结点1到结点n的一条路径，使得经过的边数尽量少，在此前提下，经过边的颜色序列的字典序最小。一对结点间可能有多变，一条边可能连接两个相同的结点。输入保证结点1可以到达结点n。颜色为1~10^9的整数。【分析】首先回顾一下第3章中介绍的“字典序”。对于字符串来说，字典序就是在字典里的顺序。例如，...
UVA 1599 Ideal Path (理想路径）
disparity_CJK的博客
10-25 724
【题意】            给一个n个点m条边（2 【分析】  1.      本题是不错的bfs题，因为数据太大，如果直接找绝对超时。   2.       题目给的n小于等于100000，所以不能用邻接矩阵来保存，只能通过邻接表，用邻接表保存还方便进              行遍历，用结构体保存邻接表，同时记录颜色的数值。  3.       题目中无向图可能有自环和重
理想路径(Ideal Path,UVa 1599)
Shiki_05的博客
11-03 823
题意：给一个n个点m条边(2 分析：两次BFS，第一次从结点n逆向BFS，得到每个节点i到结点n的最短距离step[i]，之后再从结点1正向BFS，每次到达一个新节点时保证step的值恰好减少1，如果有多种走法，则选择颜色字典序最小的走；若存在多条相同边，则一同压入队列进行判断，直至到结点n。 PS: 邻接表真的是个好东西啊 参考代码 #include #include #i
UVa 1599 理想路径 （Ideal Path）
Inuyasha__的博客
08-24 299
题目： 给一个n个点m条边的无向图，每条边上都涂有一种颜色，用数字表示。求节点1到节点n的一条路径，先保证边数尽量少，再保证经过边的字典序最小。一对节点可能有多对边，一条边可能链接两个相同节点。输入保证节点1可以到达节点n。颜色为 1 - 10^9的整数 要点 无 #include<bits/stdc++.h> #define INF 0x7fffffff using namespac...
【UVA No. 1599】理想路径 Ideal Path
谢谢你们的关注
10-04 553
【UVA No. 1599】理想路径 Ideal Path
UVa1599 - Ideal Path
Dosth_Magic
03-16 1274
#include #include #include #include using namespace std; const int maxn=100010; const int inf=1<<30; int n,vis[maxn],d[maxn]; vector g[maxn],ans; struct way{ int u,v,c; way(int u=0,int v=0,int
Ideal Path （UVA - 1599 ）
不知所云的博客
12-11 308
Ideal Path New labyrinth attraction is open in New Lostland amusement park. The labyrinth consists of n rooms connected by m passages. Each passage is colored into some color ci . Visitors of the laby...
UVa 1599 Ideal Path
QWsin的博客
03-25 659
题目 UVa 1599 Ideal Path 题解 WLGQ这个题实在是恶心了一发。一开始我在担心会T，后来发现，，并不会，只是一开始写的拙劣。结构体写了又删删了又写，数组开了又删删了又开我很无奈。 主体思想，一个d[i]记录i点到n点的最短距离。先从终点BFS一遍处理出来。 从起点开始走的话，假设当前在u点，当且仅当d[u]+1=d[v]时可以走到v点。然后
HDOJ 3760: Ideal Path
frog的小池塘
07-27 1212
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3760 题目大意： 边权全部为1的图上，每条边上有一个字母，求字典序最小的最短路 算法： 预处理出起点和终点到每个点的最短距离。 如果某点到起点和终点的距离和等于最短路的长度，那么它就有可能是最短路上的点。 这样就方便的把图划分了层次， 在这个层次图上，实质上边权就等同于点
Ideal Path理想路径，BFS与DFS（Java版）
sw1997的博客
06-24 222
非常经典的一个题目， public class IdealPath { public static int[] value; //最短路径长度 public static int[][] g; //矩阵图 public static List result = new ArrayList(); public static void main(...
Ideal Path UVA - 1599
剑似生平
03-05 190
这道题的坑是在普通BFS的基础上要查看最小权值。但是我一开始想着先用最普通的bfs来写，只是在初始化时做了一个权值的排序，然而并没有什么用，因为有可能： 但是一开始压进去的是b,它先找到e,所以这显然是错误的，所以应该转换一下思路，我们是因为不知道在第n层的最小权值应该是多少，才陷入困境，但是前提又是最短路，所以先从最后一个点开始bfs,其实这个思想是迪杰特斯特拉吧哈哈哈。然后我就醍...
uva 1599
pb1995的博客
10-31 995
原题 最近课业比较繁忙, 好久没时间写题了。 这也算是最短路径问题的改版，求满足一个条件的最短路径。 经验不足，一开始自然就想到用DFS（因为比较好写），结果当然TLE了 后来才想起来DFS的复杂度是O(N^2), 而BFS是O(N+E), 所以遇到这种规模比较大的图肯定要用BFS了, 根本不是一个数量级啊 网上虽然方法比较多, 但是描述得不是很全面, 我再来整理一下吧 主要思路是用
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值