3243. Shortest Distance After Road Addition Queries I
思路:
两种方法
1. BFS :
用一个矩阵path纪录每个城市能到哪个城市
随着queries去更新path
每更新一次，都去跑一次bfs
看从城市0到城市n-1要花多久
这样就可以得到答案了
2.
用一个矩阵distance纪录到终点城市的距离
path纪录每个城市能从哪些城市抵达
随着queries去更新path
如果queries[i][1] + 1到终点城市的距离比queries[i][0]到终点城市的距离还短
那就更新distance[queries[i][0]]
接着再去看那些能抵达queries[i][0]的城市，有没有因为这次更新distance[queries[i][0]]
使得抵达终点城市的距离能变短，如果有变短就继续更新下去
就这样跑完整个queries就可以得到答案了
golang code：
func shortestDistanceAfterQueries(n int, queries [][]int) []int {
distance := make([]int, n)
path := make([][]int, n)
distance[0] = n - 1
ans := make([]int, len(queries))
for i := 1; i < n; i++ {
path[i] = make([]int, 1)
path[i][0] = i - 1
distance[i] = n - i - 1
}
for key, val := range queries {
new_distance := distance[val[1]] + 1
path[val[1]] = append(path[val[1]], val[0])
if new_distance < distance[val[0]] {
distance[val[0]] = new_distance
update(distance, path, val[0])
}
ans[key] = distance[0]
}
return ans
}
func update(distance []int, path [][]int, pos int) {
new_distance := distance[pos] + 1
for _, val := range path[pos] {
if distance[val] > new_distance {
distance[val] = new_distance
update(distance, path, val)
}
}
}