For problem statement at 0-999/300-399/340-349/346/problemD.txt this is a correct solution, but verifier at 0-999/300-399/340-349/346/verifierD.go ends with case 1 failed: expected -1 got 1
input:
4 7
2 4
4 1
3 4
4 3
1 3
4 2
2 3
2 1
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"container/heap"
"fmt"
"os"
"strconv"
)
// Item represents a node in the priority queue
type Item struct {
node int
cost int
}
// PriorityQueue implements heap.Interface and holds Items
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].cost < pq[j].cost
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
item := x.(*Item)
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func main() {
// Use buffered I/O for speed
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
// Helper to read integers
readInt := func() int {
scanner.Scan()
val, _ := strconv.Atoi(scanner.Text())
return val
}
// Read N and M
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
m := readInt()
// Graph structures
// revAdj[v] stores list of u such that u -> v is an edge
revAdj := make([][]int, n+1)
// outDeg[u] stores the out-degree of u in the original graph
outDeg := make([]int, n+1)
for i := 0; i < m; i++ {
u := readInt()
v := readInt()
revAdj[v] = append(revAdj[v], u)
outDeg[u]++
}
s := readInt()
t := readInt()
if s == t {
fmt.Println(0)
return
}
// Dijkstra's Algorithm
// dist[u] stores the minimum orders to reach t from u
dist := make([]int, n+1)
for i := range dist {
dist[i] = -1 // Initialize with -1 (infinity)
}
// processedCount[u] tracks how many outgoing neighbors of u (in original graph) have been settled
processedCount := make([]int, n+1)
pq := &PriorityQueue{}
heap.Init(pq)
// Start from target t with cost 0
dist[t] = 0
heap.Push(pq, &Item{node: t, cost: 0})
for pq.Len() > 0 {
top := heap.Pop(pq).(*Item)
u := top.node
d := top.cost
// If current path is worse than already found, skip
if dist[u] != -1 && d > dist[u] {
continue
}
if u == s {
fmt.Println(d)
return
}
// Iterate over predecessors v (edges v -> u in original graph)
for _, v := range revAdj[u] {
processedCount[v]++
// Strategy 1: Issue an order at v to go to u.
// Cost is 1 + dist[u].
// Since we process nodes in increasing order of cost, the first time we encounter v,
// it is via its neighbor with the minimal dist.
costOrder := d + 1
if dist[v] == -1 || costOrder < dist[v] {
dist[v] = costOrder
heap.Push(pq, &Item{node: v, cost: costOrder})
}
// Strategy 2: Do not issue an order at v.
// This is valid only if all neighbors of v lead to the target safely.
// The cost is max(dist[neighbor]) for all neighbors of v.
// Since we process in increasing order, the current u is the neighbor with the largest dist seen so far.
// Once processedCount[v] == outDeg[v], we have processed all neighbors, so d is the max.
if processedCount[v] == outDeg[v] {
costNoOrder := d
if dist[v] == -1 || costNoOrder < dist[v] {
dist[v] = costNoOrder
heap.Push(pq, &Item{node: v, cost: costNoOrder})
}
}
}
}
// If s cannot reach t
fmt.Println("-1")
}
```