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)
}
}
}