← Home
For problem statement at 0-999/100-199/110-119/113/problemD.txt this is a correct solution, but verifier at 0-999/100-199/110-119/113/verifierD.go ends with case 1 failed: expected "0.12773428 0.60316989 0.10179207 0.06645483 0.10084893" got "0.126532014 0.604210723 0.101583028 0.066553773 0.101120462"
input:
5 9 2 3
4 2
4 3
3 1
2 1
3 2
5 3
4 1
5 1
5 2
0.29
0.72
0.19
0.23
0.43
exit status 1 can you fix the verifier? package main

import (
	"fmt"
	"math"
)

func main() {
	var n, m, a, b int
	if _, err := fmt.Scan(&n, &m, &a, &b); err != nil {
		return
	}
	a--
	b--

	adj := make([][]int, n)
	deg := make([]int, n)
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Scan(&u, &v)
		u--
		v--
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
		deg[u]++
		deg[v]++
	}

	p := make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i])
	}

	ans := make([]float64, n)
	if a == b {
		ans[a] = 1.0
	} else {
		P := make([][]float64, n)
		for i := 0; i < n; i++ {
			P[i] = make([]float64, n)
			P[i][i] = p[i]
			for _, v := range adj[i] {
				P[i][v] = (1.0 - p[i]) / float64(deg[i])
			}
		}

		stateIdx := make([][]int, n)
		idx := 0
		for i := 0; i < n; i++ {
			stateIdx[i] = make([]int, n)
			for j := 0; j < n; j++ {
				if i != j {
					stateIdx[i][j] = idx
					idx++
				}
			}
		}

		N := idx
		A := make([][]float64, N)
		for i := 0; i < N; i++ {
			A[i] = make([]float64, N)
		}
		B := make([]float64, N)

		for x := 0; x < n; x++ {
			for y := 0; y < n; y++ {
				if x == y {
					continue
				}
				Sp := stateIdx[x][y]
				for u := 0; u < n; u++ {
					if P[x][u] == 0 {
						continue
					}
					for v := 0; v < n; v++ {
						if P[y][v] == 0 {
							continue
						}
						if u != v {
							S := stateIdx[u][v]
							A[S][Sp] -= P[x][u] * P[y][v]
						}
					}
				}
			}
		}

		for i := 0; i < N; i++ {
			A[i][i] += 1.0
		}
		B[stateIdx[a][b]] = 1.0

		for i := 0; i < N; i++ {
			pivot := i
			for j := i + 1; j < N; j++ {
				if math.Abs(A[j][i]) > math.Abs(A[pivot][i]) {
					pivot = j
				}
			}

			A[i], A[pivot] = A[pivot], A[i]
			B[i], B[pivot] = B[pivot], B[i]

			inv := 1.0 / A[i][i]
			for j := i; j < N; j++ {
				A[i][j] *= inv
			}
			B[i] *= inv

			for j := 0; j < N; j++ {
				if i != j && A[j][i] != 0 {
					factor := A[j][i]
					for k := i; k < N; k++ {
						A[j][k] -= factor * A[i][k]
					}
					B[j] -= factor * B[i]
				}
			}
		}

		for k := 0; k < n; k++ {
			for x := 0; x < n; x++ {
				for y := 0; y < n; y++ {
					if x != y {
						S := stateIdx[x][y]
						ans[k] += B[S] * P[x][k] * P[y][k]
					}
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Printf("%.9f", ans[i])
	}
	fmt.Println()
}