这东西面试了可以搞一个# 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
相关阅读
我看三爽老大应该这么出柜徐州一男子跨区域用盐被罚5000元 (转载)RE: 吴奇隆跟金城武到底有多大？ (转载)学术版毁了 (转载)汪峰再公开示爱章子怡：到80岁，你身边还是我 (转载)一些笑话BBC:苹果总裁库克出柜将严重影响苹果在华形象 (转载)你们有没有自己乱说话然后应验了的时候聊聊俺开过的烤肉啦 (转载)石头阿姨的帖子上电视了 (转载)出轨这个概念其实就是心魔，如果本来无轨西式鬼节彰显赤裸裸丛林法则 (转载)桥布斯应该是知道库克不是直的的joke你们希望月光那个神经兮兮的老姐回来？意外得知让人内牛满面的真相。。。 (转载)库克是不是跟乔布斯搞gay？结果悲剧了国企副总回应900元请3名女子陪侍：体察民情学术版人气比军版高，发贴比军版低，说明要三人结婚怎么办?