这东西面试了可以搞一个# 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
相关阅读
丹麦发现700年前厕所 仍臭气熏天令科学家激动异常你吃什么？自己吃吗？要开始吃了吗？好吃吗？……意大利女部长在签字.....(图) (转载)10美元一个的茶叶蛋，美国人也吃不起。 (转载)又一个丧心病狂炫富的土豪学会一种新编程语言、很容易忘记学过的其他语言老故事：曾经一项研究表明，郝海东智商特别高 (转载)索男的梦想我要重新学习ABC眼保健操有没有视力保护作用不知道检察长, 普京和巴马的图片集 (图多杀猫)奥朗德带领习近平和彭丽媛参观凡尔赛宫（图） (转载)极度震惊了：卡尔加里居然是加拿大一个城市？ (转载)我和我的领导常出差洗地的出来讲讲，中国有多少人穿的起内裤？？ (转载)这些tags，如果熟悉1半内容，即可晋身码工！10万茶叶蛋派送中ZT (转载)gspc果然又是王欢喜的马甲 (转载)来，我做媒你们俩拉个手 (转载)kdevelop如何？