2017-1B Problem C

Solution that only works for the small input

// Only works for small!
// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

func test() {
	var N, Q int
	mustReadLineOfInts(&N, &Q)
	assert(Q == 1)
	maxDist := make([]int, 0, N)
	speed := make([]int, 0, N)
	for i := 0; i < N; i++ {
		var E, S int
		mustReadLineOfInts(&E, &S)
		maxDist = append(maxDist, E)
		speed = append(speed, S)
	}
	lengths := make([]int, 0, N-1)
	for i := 0; i < N; i++ {
		destsDist := mustReadLineOfIntsIntoArray()
		assert(len(destsDist) == N)
		for j := 0; j < N; j++ {
			if j == i+1 {
				lengths = append(lengths, destsDist[j])
			} else {
				assert(destsDist[j] == -1)
			}
		}
	}
	assert(len(lengths) == N-1)
	var start, dest int
	mustReadLineOfInts(&start, &dest)
	assert(start == 1)
	assert(dest == N)
	minTimes := make([]float64, N)
	for i := 0; i < N; i++ {
		minTimes[i] = -1
	}
	minTimes[0] = 0
	for reach := 0; reach < N; reach++ {
		for withHorseFrom := 0; withHorseFrom <= reach; withHorseFrom++ {
			if reach == withHorseFrom {
			} else {
				requiredDist := 0
				for i := withHorseFrom; i < reach; i++ {
					requiredDist += lengths[i]
				}
				if maxDist[withHorseFrom] < requiredDist {
					continue
				}
				time := minTimes[withHorseFrom] + float64(requiredDist)/float64(speed[withHorseFrom])
				if time < minTimes[reach] || minTimes[reach] == -1 {
					minTimes[reach] = time
				}
			}
		}
	}
	fmt.Fprintf(stdout, "%.12f\n", minTimes[N-1])
}

// boilerplate omitted...

Sample test cases given in question

3
3 1
2 3
2 4
4 4
-1 1 -1
-1 -1 1
-1 -1 -1
1 3
4 1
13 10
1 1000
10 8
5 5
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 10
-1 -1 -1 -1
1 4
4 3
30 60
10 1000
12 5
20 1
-1 10 -1 31
10 -1 10 -1
-1 -1 -1 10
15 6 -1 -1
2 4
3 1
3 2