Travel.scala

import scala.collection.SortedSet

object Travel extends App {

  def minDist(n: Int, roads: Seq[(Int, Int)], cost: IndexedSeq[IndexedSeq[Int]], queries: Seq[(Int, Int)]): Seq[Int] = {

    val graph = (Map.empty[Int, Set[(Int, Int)]].withDefaultValue(Set.empty[(Int, Int)]) /: roads.zipWithIndex) {
      case (g, ((a, b), roadIndex)) => g + (a -> (g(a) + ((b, roadIndex)))) + (b -> (g(b) + ((a, roadIndex))))
    }

    @annotation.tailrec
    def dijkstra(dist: Map[Int, Int], visitable: SortedSet[(Int, Int)], destination: Int): Option[Int] = {
      if (visitable.isEmpty) None
      else {
        val (t, u) = visitable.head
        if (u == destination) Some(t)
        else {
          val (dist1, visitable1) = ((dist, visitable.tail) /: graph(u)) {
            case ((dist, visitable), (v, roadIndex)) =>
              val alt = dist(u) + cost(roadIndex)(t % 24)
              if ((dist contains v) && alt >= dist(v)) (dist, visitable)
              else (dist + ((v -> alt)), (if (dist contains v) visitable - ((dist(v), v)) else visitable) + ((alt, v)))
          }
          dijkstra(dist1, visitable1, destination)
        }
      }
    }

    for {
      (destination, currentTime) <- queries
    } yield dijkstra(Map(1 -> currentTime), SortedSet((currentTime, 1)), destination).map(_ - currentTime) getOrElse -1
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      def readInts() = { lineIn.next().split(' ').map(_.toInt) }
      val Array(n, m, k) = readInts()
      val (roads, cost) = Vector.fill(m) {
        val Array(x, y) = readInts()
        val cost = readInts().toIndexedSeq
        ((x, y), cost)
      }.unzip
      val queries = Seq.fill(k) {
        val Array(d, s) = readInts()
        (d, s)
      }
      lineOut(s"Case #$i: ${minDist(n, roads, cost, queries).mkString(" ")}")
    }

  val filename = "A-large-practice"
  val writer = new java.io.PrintWriter(filename + ".out")
  try {
    process(io.Source.fromFile(filename + ".in").getLines) { s =>
      writer.println(s); writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }
}

TravelTest.scala

import org.scalatest._

import Travel._

class TravelTest extends FunSuite with Matchers {

  test("sample #1") {
    assert(minDist(3, Seq((1, 2), (1, 3), (2, 3)), Vector(Vector.fill(24)(1), Vector.fill(24)(3), Vector.fill(24)(1)), Seq((2, 1), (3, 3))) === Seq(1, 2))
  }

  test("sample #2") {
    assert(minDist(3, Seq((1, 2)), Vector(Vector.fill(24)(1)), Seq((2, 2), (3, 4))) === Seq(1, -1))
  }


  test("sample case") {
    val input = """3
3 3 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 
2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1
3 3
3 1 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2
3 4
3 3 3
1 2
7 23 23 25 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
1 3
10 11 15 26 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
2 3
7 29 28 27 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
2 14
3 3
3 21""".lines

    val expected = """Case #1: 1 2
Case #2: 1 -1
Case #3: 17 26 13""".lines

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("A-small-practice.in").getLines()
    val expected = io.Source.fromFile("A-small-practice.out").getLines()

    lineComparison(input, expected)
  }

  ignore("full large case") {
    val input = io.Source.fromFile("A-large-practice.in").getLines()
    val expected = io.Source.fromFile("A-large-practice.out").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}