← Home
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 All tests passed can you fix the verifier? package main

import (
	"container/heap"
	"fmt"
	"io"
	"os"
)

type Item struct {
	node int
	dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	buf, _ := io.ReadAll(os.Stdin)
	idx := 0
	readInt := func() int {
		for idx < len(buf) && (buf[idx] < '0' || buf[idx] > '9') {
			idx++
		}
		if idx >= len(buf) {
			return 0
		}
		res := 0
		for idx < len(buf) && buf[idx] >= '0' && buf[idx] <= '9' {
			res = res*10 + int(buf[idx]-'0')
			idx++
		}
		return res
	}

	n := readInt()
	m := readInt()
	if n == 0 {
		return
	}

	head := make([]int, n+1)
	for i := range head {
		head[i] = -1
	}
	next := make([]int, m)
	to := make([]int, m)
	outDegree := make([]int, n+1)

	for i := 0; i < m; i++ {
		u := readInt()
		v := readInt()
		outDegree[u]++
		to[i] = u
		next[i] = head[v]
		head[v] = i
	}

	s := readInt()
	t := readInt()

	unsettledOut := make([]int, n+1)
	copy(unsettledOut, outDegree)

	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = -1
	}

	pq := make(PriorityQueue, 0, m)
	heap.Push(&pq, Item{node: t, dist: 0})

	for pq.Len() > 0 {
		curr := heap.Pop(&pq).(Item)
		if dp[curr.node] != -1 {
			continue
		}
		dp[curr.node] = curr.dist
		if curr.node == s {
			break
		}
		for e := head[curr.node]; e != -1; e = next[e] {
			prev := to[e]
			unsettledOut[prev]--
			if unsettledOut[prev] == outDegree[prev]-1 {
				heap.Push(&pq, Item{node: prev, dist: curr.dist + 1})
			}
			if unsettledOut[prev] == 0 {
				heap.Push(&pq, Item{node: prev, dist: curr.dist})
			}
		}
	}

	fmt.Println(dp[s])
}