2699. Modify Graph Edge Weights
给一个无向图有n个节点
再给一个edges矩阵 : edges[i]=[a_i,b_i,w_i]
w_i为a_i、b_i两个节点间边的权重
有些边的权重为-1
可以将权重为-1的边更改为1~2*10^9间的任意数字
请透过更改-1的边使source到destination的最短路径=target
并回传最短路径为target时的edges
如果无法达成回传空矩阵
思路:
写到一半放弃，直接看答案，有够难
我是看到两个解法
第一种解法
用Dijkstra算法去计算最短路径，并将-1视为不可通过的边
当在没有修改任何edge的情况下，
(1)如果得到的最短路径<targer，则回传空矩阵
(2)如果最短路径==target，则将所有-1的edges改为target+1，并回传edges
(3)如果最短路径>target
去遍历edges只要遇到-1的边就将其改为1再去跑Dijkstra
如果得到的答案还是大于target，那这个边就保持为1
并继续遍历
如果得到的答案小于target那就将这个边改成target-最短路径+1
并将其他边改成target+1(确保不会有其他最短路径)
这样就可以得到答案了
如果遍历到最后没找到就回传空矩阵
第二种解法
第二种其实我看不太懂
就是先将所有-1的edges视为1去跑一次Dijkstra
将这次到各点的最短路径记录起来:distance1
并得到第一次的最短路径shortest_path1
(1)如果shortest_path1>target回传空矩阵
(2)shortest_path1与target的差值:different
进行第二次Dijkstra，这次用distance来记录到各点的最短路径，这次比较特别
当遇到edge为-1时试着去将边的权重增加，让最短路径可以满足target
这要透过第一次得到的distance1来计算
newweight=distance1[next_node]+different-distance2[current_node]
就这样算出第二次Dijkstra的最短路径:shortest_path2
(1)shortest_path2<target (这是在没修改edges的情况下就从在最短路径的情况)
回传空矩阵
(2)将剩余权重为-1的edges修改为target+1
就可以得到答案了
golang code :
这是第二种解法
type Edge struct {
next_node int
idx int
}
type Vertex struct {
cur_node int
cur_distance int
}
type minheap []*Vertex
func (this minheap) Len() int { return len(this) }
func (this minheap) Less(i, j int) bool { return this[i].cur_distance < this[j
].cur_distance }
func (this minheap) Swap(i, j int) { this[i], this[j] = this[j], this[i]
}
func (this *minheap) Pop() any {
n := len(*this)
res := (*this)[n-1]
*this = (*this)[:n-1]
return res
}
func (this *minheap) Push(x any) {
*this = append(*this, x.(*Vertex))
}
func modifiedGraphEdges(n int, edges [][]int, source int, destination int,
target int) [][]int {
rec := make([][]Edge, n)
distance := make([][2]int, n)
for i := 0; i < n; i++ {
distance[i] = [2]int{math.MaxInt32, math.MaxInt32}
}
for key, val := range edges {
rec[val[0]] = append(rec[val[0]], Edge{val[1], key})
rec[val[1]] = append(rec[val[1]], Edge{val[0], key})
}
Dijkstra(rec, source, destination, n, edges, distance, 0, 0)
tmp := distance[destination][0]
diff := target - tmp
if diff < 0 {
return [][]int{}
}
Dijkstra(rec, source, destination, n, edges, distance, 1, diff)
tmp = distance[destination][1]
if target > tmp {
return [][]int{}
}
for key, val := range edges {
if val[2] == -1 {
edges[key][2] = 1+target
}
}
return edges
}
func Dijkstra(rec [][]Edge, source int, destination int, n int, edges [][]int,
distance [][2]int, run int, diff int) {
min_heap := minheap{&Vertex{source, 0}}
distance[source][run] = 0
for min_heap.Len() > 0 {
cur_vertex := heap.Pop(&min_heap).(*Vertex)
if cur_vertex.cur_distance > distance[cur_vertex.cur_node][run] {
continue
}
for _, val := range rec[cur_vertex.cur_node] {
weight := edges[val.idx][2]
if edges[val.idx][2] == -1 {
weight = 1
}
if run == 1 && edges[val.idx][2] == -1 {
new_weight := distance[val.next_node][0] + diff - distance[cur_vertex.cur_
node][1]
if new_weight >= weight {
weight = new_weight
edges[val.idx][2] = weight
}
}
tmp := cur_vertex.cur_distance + weight
if distance[val.next_node][run] > tmp {
distance[val.next_node][run] = tmp
heap.Push(&min_heap, &Vertex{val.next_node, tmp})
}
}
}
}