ARC083[D].go

ARC083[D].go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// global
var sc = bufio.NewScanner(os.Stdin)

func main() {
	var N int
	fmt.Scan(&N)

	var A [][]int
	for i := 0; i < N; i++ {
		stt := strings.Split(nextLine(), " ")
		A = append(A, Filter(stt))
	}
	//fmt.Println(A)

	ans := 0
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			if i <= j {
				continue
			}
			ret := 100000000000
			for k := 0; k < N; k++ {
				if i == k || j == k {
					continue
				}

				if A[i][j] > A[i][k]+A[k][j] {
					fmt.Println(-1)
					os.Exit(0)
				} else {
					ret = min(ret, A[i][k]+A[k][j])
				}
			}
			if A[i][j] < ret {
				//fmt.Println("found",i,j)
				ans += A[i][j]
			}
		}
	}
	fmt.Println(ans)
}

// ----------------------------------//
//              utils                //
// ----------------------------------//

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func Filter(s []string) []int {
	var p []int // == nil
	var val int
	for _, v := range s {
		val, _ = strconv.Atoi(v)
		p = append(p, val)
	}
	return p
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}