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