胸器较大的JM晚上睡觉要戴胸衣吗 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

胸器较大的JM晚上睡觉要戴胸衣吗

胸器较大的JM晚上睡觉要戴胸衣吗# Fashion - 美丽时尚

m*a2011-02-28 08:02

1 楼

有N个城市（A,B,C,D,E,F,......）给出如下两种指令：
1. make X Y Z
means 在X,Y城市之间修一条路，路的权重是Z
2. check X Y
查看X Y城市之间权重最小的路，并输出，如果没有路就输出-1
现在给出N个城市，然后有一组输入指令，如：
make A B 500
make A C 1000
check A D
make B D 700
check A D
make C E 200
check A E
........
每次碰到check指令就要输入相应的值，如：
-1
500
200
请问除了每次check的时候都DFS外有没有比较好的算法？

s*n2011-02-28 08:02

2 楼

不戴的话会不会对形状有不好的影响，毕竟睡觉时间占了有三分之一

w*d2011-02-28 08:02

3 楼

mark，等大牛。

a*n2011-02-28 08:02

4 楼

据说睡觉穿内衣，乳腺癌发病率会增高。

p*n2011-02-28 08:02

5 楼

DFS 不能保证最短路径，找最短路径用best first search。
搜索看看path planning algorithms，有一些很nb的算法，比如Life-long planning A
＊ ( LPA*) 不过对于面试来讲有点杀机用牛刀了。

【在 m******a 的大作中提到】

: 有N个城市（A,B,C,D,E,F,......）给出如下两种指令：
: 1. make X Y Z
: means 在X,Y城市之间修一条路，路的权重是Z
: 2. check X Y
: 查看X Y城市之间权重最小的路，并输出，如果没有路就输出-1
: 现在给出N个城市，然后有一组输入指令，如：
: make A B 500
: make A C 1000
: check A D
: make B D 700

r*92011-02-28 08:02

6 楼

不用带，仰着睡

a*52011-02-28 08:02

7 楼

MAKE O(N) CHECK O(1)的行吗

o*l2011-02-28 08:02

8 楼

如果倒立着睡是不是越睡越有型？

y*t2011-02-28 08:02

9 楼

“权重最小的路”这里题意描述能否更准确一点？我看下面的例子，好像是X,Y之间的
路径上的权重最小的边？
问题1: 如果XY之间有多条路径是输出最小值么？
比如下面样例
make A B 200
make A C 100
make B D 300
make C D 500
check A D // 输出100么？
问题2：路径必须是简单路径么？就是说如果一条死胡同里有一个短边，算不算？
下面样例：
make A B 200
make A C 100
make B D 300
check A D // 输出100还是200？

f*s2011-02-28 08:02

10 楼

那样能睡着么

【在 o******l 的大作中提到】

: 如果倒立着睡是不是越睡越有型？

m*a2011-02-28 08:02

11 楼

问题1：
对的，就是输出最小值
问题2:
死胡同不算，一定要是可以到达的路径中的最小的一段

【在 y****t 的大作中提到】

: “权重最小的路”这里题意描述能否更准确一点？我看下面的例子，好像是X,Y之间的
: 路径上的权重最小的边？
: 问题1: 如果XY之间有多条路径是输出最小值么？
: 比如下面样例
: make A B 200
: make A C 100
: make B D 300
: make C D 500
: check A D // 输出100么？
: 问题2：路径必须是简单路径么？就是说如果一条死胡同里有一个短边，算不算？

i*r2011-02-28 08:02

12 楼

睡姿还有规定？
那还怎么睡啊？

m*a2011-02-28 08:02

13 楼

展开说说吧，

【在 a********5 的大作中提到】

: MAKE O(N) CHECK O(1)的行吗

t*e2011-02-28 08:02

14 楼

睡觉穿胸衣不健康，会加大患乳腺癌的几率。

a*52011-02-28 08:02

15 楼

我想的是：
定义f[i][j] = i到j的最小权重和（带权最短路）初始化成正无穷
那么当make(i, j, t)的时候：
对于所有的节点k
if f[k][i] + t < f[k][j] f[k][j] = ...
if t + f[j][k] < f[i][k] f[i][k] = ...
当然是无向图，可以做些处理或者干脆更新两遍弄成对称矩阵。这个应该无所谓。所以
每次更新是o(n)
然后check(a,b)直接f[a][b]就可以了.

【在 m******a 的大作中提到】

: 展开说说吧，

f*82011-02-28 08:02

16 楼

健康更重要

m*a2011-02-28 08:02

17 楼

恩，确实比爆搜好多了，不过这题要的不是权重和，要的是最小权重，不过按这个思
路也是可以的。

【在 a********5 的大作中提到】

: 我想的是：
: 定义f[i][j] = i到j的最小权重和（带权最短路）初始化成正无穷
: 那么当make(i, j, t)的时候：
: 对于所有的节点k
: if f[k][i] + t < f[k][j] f[k][j] = ...
: if t + f[j][k] < f[i][k] f[i][k] = ...
: 当然是无向图，可以做些处理或者干脆更新两遍弄成对称矩阵。这个应该无所谓。所以
: 每次更新是o(n)
: 然后check(a,b)直接f[a][b]就可以了.