← Home
For problem statement at 1000-1999/1400-1499/1450-1459/1450/problemE.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1450-1459/1450/verifierE.go ends with REFERENCE_SOURCE_PATH environment variable not set
exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, m int
	if _, err := fmt.Fscan(in, &n, &m); err != nil {
		return
	}

	adj := make([][]int, n+1)
	const INF = 1e9
	d := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		d[i] = make([]int, n+1)
		for j := 1; j <= n; j++ {
			if i == j {
				d[i][j] = 0
			} else {
				d[i][j] = INF
			}
		}
	}

	for k := 0; k < m; k++ {
		var u, v, b int
		fmt.Fscan(in, &u, &v, &b)
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)

		if b == 1 {
			if 1 < d[u][v] {
				d[u][v] = 1
			}
			if -1 < d[v][u] {
				d[v][u] = -1
			}
		} else {
			if 1 < d[u][v] {
				d[u][v] = 1
			}
			if 1 < d[v][u] {
				d[v][u] = 1
			}
		}
	}

	color := make([]int, n+1)
	color[1] = 1
	q := []int{1}
	isBipartite := true
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		for _, v := range adj[u] {
			if color[v] == 0 {
				color[v] = 3 - color[u]
				q = append(q, v)
			} else if color[v] == color[u] {
				isBipartite = false
			}
		}
	}

	if !isBipartite {
		fmt.Println("NO")
		return
	}

	for k := 1; k <= n; k++ {
		for i := 1; i <= n; i++ {
			for j := 1; j <= n; j++ {
				if d[i][k] != INF && d[k][j] != INF {
					if d[i][j] > d[i][k]+d[k][j] {
						d[i][j] = d[i][k] + d[k][j]
					}
				}
			}
		}
	}

	for i := 1; i <= n; i++ {
		if d[i][i] < 0 {
			fmt.Println("NO")
			return
		}
	}

	maxDiff := -1
	bestU := 1
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if d[i][j] != INF && d[i][j] > maxDiff {
				maxDiff = d[i][j]
				bestU = i
			}
		}
	}

	fmt.Println("YES")
	fmt.Println(maxDiff)
	out := bufio.NewWriter(os.Stdout)
	for i := 1; i <= n; i++ {
		fmt.Fprintf(out, "%d ", d[bestU][i])
	}
	fmt.Fprintln(out)
	out.Flush()
}