这东西面试了可以搞一个# Joke - 肚皮舞运动
f*n
1 楼
题目大意就是一个图，每条边有正的权重，同时每条边有一个属性，属于一个集合中的
一个(比如{a,b,c})。
求从一个点到另一个点的路径，要求经过的边满足一些条件，比如至少有一条边的属性
是a有一条是b。
谢谢！
一个(比如{a,b,c})。
求从一个点到另一个点的路径，要求经过的边满足一些条件，比如至少有一条边的属性
是a有一条是b。
谢谢！
k*r
2 楼
嗯
p*2
3 楼
DFS吗。
【在 f***n 的大作中提到】
: 题目大意就是一个图，每条边有正的权重，同时每条边有一个属性，属于一个集合中的
: 一个(比如{a,b,c})。
: 求从一个点到另一个点的路径，要求经过的边满足一些条件，比如至少有一条边的属性
: 是a有一条是b。
: 谢谢！
r*e
4 楼
拍摄的质量应该不会太好!
【在 k***r 的大作中提到】
: 嗯
【在 k***r 的大作中提到】
: 嗯
h*e
5 楼
不是BFS吗？一直找到目标点，如果限制条件不满足的话，回溯到
次优点再找。
次优点再找。
s*l
6 楼
跟面试什么关系？
f*n
7 楼
BFS吧？但是对一个图最简单的bfs方法是什么？
【在 p*****2 的大作中提到】
:
: DFS吗。
【在 p*****2 的大作中提到】
:
: DFS吗。
p*p
8 楼
如果是苹果做，那就肯定好
【在 r*********e 的大作中提到】
: 拍摄的质量应该不会太好!
【在 r*********e 的大作中提到】
: 拍摄的质量应该不会太好!
f*n
9 楼
我的第一反应也是bfs+dp，但是具体怎么做？怎样对一个图做bfs是最优的？
谢谢。
【在 h****e 的大作中提到】
: 不是BFS吗？一直找到目标点，如果限制条件不满足的话，回溯到
: 次优点再找。
谢谢。
【在 h****e 的大作中提到】
: 不是BFS吗？一直找到目标点，如果限制条件不满足的话，回溯到
: 次优点再找。
p*2
10 楼
图有没有回路？我第一想法就是DFS做brute force。
p*2
11 楼
BFS也不容易呀。找到了不一定是最短。
p*2
12 楼
不知道Dijstra变形如何，找到了如果不满足条件继续找。
f*n
13 楼
搞定了，用bellman ford的变种，复杂度是O(m*n*s)，m是边数，n是点数，s是集合大
小。
基本上跟带负权重的最短路很类似，除了dp的状态多出一维来保存集合状态。
另外，原来这种问题不是bfs可以搞定的，还是得边数*点数的复杂度一条边一条边的走啊
【在 p*****2 的大作中提到】
: 不知道Dijstra变形如何，找到了如果不满足条件继续找。
小。
基本上跟带负权重的最短路很类似，除了dp的状态多出一维来保存集合状态。
另外，原来这种问题不是bfs可以搞定的，还是得边数*点数的复杂度一条边一条边的走啊
【在 p*****2 的大作中提到】
: 不知道Dijstra变形如何，找到了如果不满足条件继续找。
p*2
14 楼
走啊
你只是做哪里的题呀？bellman ford我还没学过。这算法很有用吗？
【在 f***n 的大作中提到】
: 搞定了，用bellman ford的变种，复杂度是O(m*n*s)，m是边数，n是点数，s是集合大
: 小。
: 基本上跟带负权重的最短路很类似，除了dp的状态多出一维来保存集合状态。
: 另外，原来这种问题不是bfs可以搞定的，还是得边数*点数的复杂度一条边一条边的走啊
w*x
15 楼
要我就DFS的brutal force, 每次到达终点后检查是否满足条件再在所有满足条件的结
果中找最优
果中找最优
p*2
16 楼
摁。e跟我ie一个l思路
【在 w****x 的大作中提到】
: 要我就DFS的brutal force, 每次到达终点后检查是否满足条件再在所有满足条件的结
: 果中找最优
y*g
17 楼
CLRS里面的啊，all pair shortest path 。代码简单。
TC砍图论题目必备
【在 p*****2 的大作中提到】
:
: 摁。e跟我ie一个l思路
TC砍图论题目必备
【在 p*****2 的大作中提到】
:
: 摁。e跟我ie一个l思路
p*2
18 楼
我就学了Floyd-Warshall和Dijkstra。 还没碰到需要那个的题。有时间得看看。
【在 y*******g 的大作中提到】
: CLRS里面的啊，all pair shortest path 。代码简单。
: TC砍图论题目必备
s*t
19 楼
BF也是单源最短，你说的是floyd吧: )
另外同问楼主做的哪个题目？
poj的一个题目跟您描述的有点像，初始有一个设定——身上有K块钱，过一个点要交一
个点的过路费，问能到终点且路径最短的走法。
http://poj.org/problem?id=1724
【在 y*******g 的大作中提到】
: CLRS里面的啊，all pair shortest path 。代码简单。
: TC砍图论题目必备
另外同问楼主做的哪个题目？
poj的一个题目跟您描述的有点像，初始有一个设定——身上有K块钱，过一个点要交一
个点的过路费，问能到终点且路径最短的走法。
http://poj.org/problem?id=1724
【在 y*******g 的大作中提到】
: CLRS里面的啊，all pair shortest path 。代码简单。
: TC砍图论题目必备
y*g
20 楼
记混了，，:(
【在 s******t 的大作中提到】
: BF也是单源最短，你说的是floyd吧: )
: 另外同问楼主做的哪个题目？
: poj的一个题目跟您描述的有点像，初始有一个设定——身上有K块钱，过一个点要交一
: 个点的过路费，问能到终点且路径最短的走法。
: http://poj.org/problem?id=1724
【在 s******t 的大作中提到】
: BF也是单源最短，你说的是floyd吧: )
: 另外同问楼主做的哪个题目？
: poj的一个题目跟您描述的有点像，初始有一个设定——身上有K块钱，过一个点要交一
: 个点的过路费，问能到终点且路径最短的走法。
: http://poj.org/problem?id=1724
相关阅读
狗急跳墙，鸡呢？我爱讲笑话(转载)Re: 张学良到底是个什么样的人（原创） (转载)实话总是伤人 zz今天还有人要撕的吗？为什么说木星是太阳 系内最大的“情种” 科技日报 ugmbbc 1天1小时前 作为太阳系内最特殊的气态巨行星，木星一直以来都勾起了人们的无限遐想。据美国国家航空航天局（NASA）消息，“朱诺”号木星探测器历经5年旅程，终 于不辱使命，将于美国东部时间7月4日晚进入木星轨道，人类得以更近距离地与木星亲密接触。“块头”大、自转快、磁场强、大红斑最有名、自带光环、卫星 “情人”最多…… http://cms-bucket.nosdn.127.net/catchpic/f/f3/f3dc7a450779eb216ca02fbd43b7dfc5.jpg 作为太阳系内最特殊的气态巨行星，木星一直以来都勾起了人们的无限遐想。据美国国家航空航天局（NASA）消息，“朱诺”号木星探测器历经5年旅程，终于不辱使命，将于美国东部时间7月4日晚进入木星轨道，人类得以更近距离地与木星亲密接触。那么，木星究竟是一个什么样的存在，值得科学家们跨越数百年时间、跨越数亿万公里的空间，苦苦追寻呢? “块头”最大 据NASA官网介绍，木星是太阳系八大行星中体积最大、自转最快的行星，从内向外的第五颗行星。木星的赤道约为14.3万公里。木星如此大，太阳系内所有其他行星都能塞进木星里面，木星“大肚”能容超过1000颗行星。木星的质量是地球质量的318倍，是太阳系内所有其他行星质量总和的2.5倍。 木星距离太阳的平均距离是5.2个天文单位（1个天文单位为太阳与地球之间的距离，约为1.496亿千米），因此，其与太阳间的距离为地球与太阳之间距离的5倍多。当我们从地球上看时，它是夜空中亮度排第二的行星，排在“夜空中最亮行星”金星之后。 木星大气层由86%的氢气和14%的氦气组成。这颗行星的表面覆盖着厚厚的、棕黄色和白色相间的云层。 天文学家们将木星称为“失败的恒星”，但这一描述并不恰当。尽管有一点毋庸置疑：就像恒星一样，木星富含氢气和氦气，但木星的质量不足以在其内部触发核聚变反应。 http://cms-bucket.nosdn.127.net/catchpic/0/07/078c2139fc05dec95de910e44c7e56dc.jpg 自转最快 磁场最强 木星是太阳系内自转最快的行星。鉴于其大“块头”和傲视群雄的体重，木星的移动速度非常快。实际上，其自转速度为4.53万公里/小时（12.6公里/秒），一次自转只需10小时，因此，木星的一天只有10个小时。木星的轨道为椭圆或橄榄型，绕太阳旋转一次所需的时间是地球绕太阳旋转一次所需时间的12倍，因此，木星上的一年等于地球上的12年。 木星云层的温度约为零下145摄氏度。木星中央附近的温度非常高，核心温度约为2.4万摄氏度，比太阳表面还热。 如果一个人能站在木星大气层顶端，那么，它受到的引力约为在地球表面引力的2.4倍，因此，在地球上重100磅（约91斤）的人在木星上重达240磅（218斤）。 快速的旋转也助力木星获得了强大的磁场，木星拥有太阳系内最强大的磁场。在木星云层之下是一个巨大的液态金属氢组成的海洋。随着木星不断旋转，旋转的液态金属海洋制造出了这个强磁场，木星的磁场强度是地球磁场的2万多倍。 天文学家们认为，这一磁场会捕获源自木卫一上火山喷发的氧化硫粒子，这些氧化硫粒子与源自木星大气层的氢离子一起，在木星赤道面形成了一个磁层。 这一磁层与太阳风的交互作用会生成一个弓型冲击波，这是一个危险的辐射带，会破坏航天器。木星的四大卫星都在磁层内旋转，这会保护其远离太阳风的冲击，但是，也会使人们很难在这些卫星上建造前哨基地。 http://cms-bucket.nosdn.127.net/catchpic/e/e6/e68cb60f281e5c5f3de6b98c0da804c6.jpg 大红斑最有名 木星最引人注目的特征是其大红斑，它是一种反气旋风暴，位于木星赤道的南部，直径为2.4万千米，高度为1.2万到1.4万千米。在大红斑最宽的点，风暴大约是地球直径的3.5倍，足以容纳2到3个地球直径大小的行星。 木星是一个多风的行星，风力从192英里（309公里）/小时到超过400英里（644公里）/小时。 大红斑据信已经存在了至少360多年，1665年，意大利天文学家乔凡尼?卡西尼发现了它的存在。到20世纪，天文学家们开始认为，大红斑是一种风暴，由木星的湍流和快速运动的大气层造成。“旅行者1号”探测器证实了这一理论，1979年3月，“旅行者1”号在掠过该行星时，观测到了大红斑。 然而，大红斑显然一直在萎缩，根据“卡西尼”号的观测，在17世纪时，大红斑的大小为4万千米，几乎为目前的2倍。天文学家们并不知道是否或何时它将完全消失，但他们确信，另一个大红斑可能会出现在木星的某个地方。 自带光环 当人们想到有环的天体系统时，土星首先印入脑海。但实际上，天王星和木星也有自己的环。木星是第三个被发现有环的行星，因为其环极其暗淡。1979年，NASA的“旅行者1号”航天器发现木星有三个小环——最内层是由光晕粒子组成的环；中间是相当明亮的主环；外部是一个轻薄的类似薄纱的环。 科学家们普遍认为，这些环可能由其陨石撞击木星的卫星时，卫星喷射出的物质组成。实际上，主环被认为由来自木卫十五和木卫十六的物质组成；而薄纱环的物质来自木卫十四和木卫五。 http://cms-bucket.nosdn.127.net/catchpic/e/e2/e2464c5fa6006b79fcd4bdde61e61b47.jpg 肉眼可见 在大多数时候，木星不仅肉眼可见，还是全天第二亮星，在行星中仅次于金星，在所有天体中仅次于太阳、月亮和金星，居第四位，比太阳外的所有恒星都要亮得多。 不仅木星本身肉眼可见，在某些极端情况下，连木星的某些卫星都可以用肉眼看见。 “情人”最多（卫星最多） 目前，木星是太阳系拥有卫星数最多的行星，2012年2月23日科学家称发现了木星2颗新卫星，累计卫星达68颗。木星的英文名Juppiter（朱庇特）代表着古罗马神话中的众神之王，木星的卫星全部以朱庇特的情人命名。 按照距离木星的顺序，木星的四大“情人”分别为木卫一“依娥（lo）”、木卫二“欧罗巴（Europa）”、木卫三“伽倪墨得斯（Ganymede）”、木卫四 “卡利斯托（Callisto）”。这四颗卫星通常被称为“伽利略卫星”。伽利略发现，虽然木星在空中移动，但这些卫星仍环绕木星公转，从而得到支持哥白尼日心说的论据，即并非所有天体均环绕地球旋转。 木星最大的卫星是木卫三，它也是太阳系内最大的卫星，直径为5262千米。木卫三比水星还大，“块头”是火星的四分之三。木卫三是太阳系内唯一拥有自己磁场的卫星。木卫三和木卫四上有很多由冰块和岩石构成的环形山。 木卫一拥有很多活火山。这些火山产生了含硫的气体。木卫一橙黄色的表面很有可能由火山喷发出的硫组成。木卫二是“伽利略”卫星家族中最小的。木卫二的表面主要是水冰。冰下可能是水或冰组成的海洋，其含水量是地球的2倍。仔细想想， 我强奸过男的， 很多次了 (转载)现在的美国妇女和60年代的男人体重一样又见杀猪之刃！ (转载)那个尼姑太牛 (转载)Re: 老大爷和老猫都是夫妻公用马甲！ (转载)笑死我了 (转载)哈哈一笑 轻松愉快 Zz最嚣张的段子 (转载)Re: 我想和拼图深刻的交流一下现代物理学的现状与未来 (转载)月光妹妹是2014年入学，2016年毕业1979年，赵家人的第一桶金 (转载)海外华人要团结，募捐请个好律师吧 (转载)喜欢谁就娶谁Re: 其实很多男女干的时候就是处于要与不要的量子纠缠态 (转载)