s******e
发帖数: 108 | 1 Given a matrix, each element is either s(start), a(availbe), b(block).
There are many s in the matrix,
compute the shortest path of each a(availbe) element.
distance from s or a to ajacent element is 1。
from s or a to b（block) is +ulimited.
compute the shortest distance from a(available) element to all s (start)
node
for exmaple.
s a a a s
the result would be
0 1 2 1 0
for
s b s b s
a b a b a
a b a b a
a a a a a
the result would be
0 + 0 + 0
1 + 1 + 1
2 + 2 + 2
3 4 3 4 3 |
B*******1
发帖数: 2454 | 2 我的第一想法是
方法1：
根据矩阵建立一个adj matrix，
然后对每一个s，跑dijkstra，算到每一个a的最短距离，
对于每一个a，如果新的s算出来的最短距离更加小，就更新它的最短距离。
方法2：
建立adj matrix
跑flyoyd- warshal, 算每2点之间最短距离，
对每一个a，找到所有s的距离中最小的那一个。 |
b*******y
发帖数: 232 | 3 一开始所有a的值+infty，s的值为0.
然后对每个s开始广播距离(bfs)，然后update a的值(也就是距离）
如果a的值没有update，就没必要继续广播下去了。
【在 s******e 的大作中提到】
: Given a matrix, each element is either s(start), a(availbe), b(block).
: There are many s in the matrix,
: compute the shortest path of each a(availbe) element.
: distance from s or a to ajacent element is 1。
: from s or a to b（block) is +ulimited.
: compute the shortest distance from a(available) element to all s (start)
: node
: for exmaple.
: s a a a s
: the result would be
|
r*****s
发帖数: 51 | |
D*******e
发帖数: 151 | 5 我也这样想的。对每个S做BFS。对每个A，如果算出来的新的距离比原来的小，就更新。跟Bayesian1
说的跑Dijskra是一样的。
如果把所有S放在一起看作一个S做BFS，可能会快，能证明正确性吗？
【在 b*******y 的大作中提到】
: 一开始所有a的值+infty，s的值为0.
: 然后对每个s开始广播距离(bfs)，然后update a的值(也就是距离）
: 如果a的值没有update，就没必要继续广播下去了。
|
m**q
发帖数: 189 | 6 把所有s放在一起是个好主意，直观上应该是正确的
新。跟Bayesian1
【在 D*******e 的大作中提到】
: 我也这样想的。对每个S做BFS。对每个A，如果算出来的新的距离比原来的小，就更新。跟Bayesian1
: 说的跑Dijskra是一样的。
: 如果把所有S放在一起看作一个S做BFS，可能会快，能证明正确性吗？
|
u***q
发帖数: 21 | 7 Since the distance is 1 everywhere for s, a. Any a will be updated with the
shortest distance the first time it's visited. So start from all s should
work.
【在 m**q 的大作中提到】
: 把所有s放在一起是个好主意，直观上应该是正确的
:
: 新。跟Bayesian1
|
D*******e
发帖数: 151 | 8 Agree
the
【在 u***q 的大作中提到】
: Since the distance is 1 everywhere for s, a. Any a will be updated with the
: shortest distance the first time it's visited. So start from all s should
: work.
|
