// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func findCity(n int, edges [][]int, distanceLong int) int {
	distance := make([][]int, n)
	for i := range distance {
		distance[i] = make([]int, n)
		for j := range distance[i] {
			distance[i][j] = 10000000
		}
	}
	for i := range distance {
		distance[i][i] = 0
	}
	for i := range edges {
		distance[edges[i][0]][edges[i][1]] = edges[i][2]
		distance[edges[i][1]][edges[i][0]] = edges[i][2]
	}
	for k := range distance {
		for i := range distance {
			for j := range distance {
				distance[i][j] = min(distance[i][k]+distance[k][j], distance[i][j])
			}
		}
	}

	res := make([]int, n)
	for i := range distance {
		for j := range distance[i] {
			if i != j && distance[i][j] <= distanceLong {
				res[i]++
			}
		}
	}
	result := 0
	cur := res[0]
	for i := range res {
		if res[i] <= cur {
			result = i
			cur = res[i]
		}
	}
	return result
}

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

func main() {
	edges := [][]int{{0, 1, 2}, {1, 2, 3}, {2, 3, 4}, {1, 3, 1}}
	n := 4
	distanceLong := 4
	res := findCity(n, edges, distanceLong)
	fmt.Println(res)
}

//$ go run interview9-1.go
//2