SpaceshipDefence.scala

import scala.collection.mutable.PriorityQueue

object SpaceshipDefence extends App {

  type Graph = Map[String, Set[(String, Int)]]

  def buildGraph(rooms: IndexedSeq[String], lifts: Map[Int, Set[(Int, Int)]]): Graph = {
    for ((from, vs) <- lifts) yield (rooms(from) -> {
      for ((to, w) <- vs) yield (rooms(to), w)
    })
  } withDefaultValue Set.empty[(String, Int)]

  def shortestTime(g: Graph, from: String, to: String): Int = {

    val pq = new PriorityQueue[(Int, String)]()
    pq += ((0, from))
    def loop(currentTime: Int, map: Map[String, Int]): Int = {

      println(pq)

      if (pq.isEmpty) -1
      else {

        val (t, c) = pq.dequeue

        if (c == to) currentTime + t
        else {
          for { (c0, t0) <- g(c) if !(map contains c0) } {
            pq += ((t0 + currentTime, c0))
          }
          loop(currentTime, map ++ (for ((c0, t0) <- g(c) if !(map contains c0)) yield (c0, t0 + currentTime)))
        }

      }

    }

    loop(0, Map(from -> 0))
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val n = lineIn.next().toInt
      val rooms = "" +: Vector.fill(n)(lineIn.next())

      val m = lineIn.next().toInt
      val lifts = Vector.fill(m) {
        val Array(a, b, t) = lineIn.next().split(' ').map(_.toInt)
        (a, b, t)
      }.groupBy(_._1).mapValues(_.map { case (a, b, t) => (b, t) }.toSet)

      val s = lineIn.next().toInt
      val soldiers = Vector.fill(s) {
        val Array(start, end) = lineIn.next().split(' ').map(_.toInt)
        (start, end)
      }

      val g = buildGraph(rooms, lifts)

      lineOut(s"Case #$i:")
      for ((start, end) <- soldiers) lineOut(shortestTime(g, rooms(start), rooms(end)).toString)

    }

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

}

SpaceshipDefenceTest.scala

import org.scalatest._

import SpaceshipDefence._

class SpaceshipDefenceTest extends FunSuite {

  test("sample case #1") {
    val rooms = Vector("", "gl", "t3", "t3")
    val lifts = Map(1 -> Set((1, 21), (2, 217)),
        3 -> Set((2, 567)))
    val g = buildGraph(rooms, lifts)
    
    assert(g === Map("gl" -> Set(("gl", 21), ("t3", 217)),
        "t3" -> Set(("t3", 567))))
    
    assert(shortestTime(g, rooms(2), rooms(1)) === -1)
    assert(shortestTime(g, rooms(2), rooms(3)) === 0)
    
  }
  
  
  test("sample case") {
    val input = """3
3
gl
t3
t3
3
1 2 217
3 2 567
1 1 21
2
2 1
2 3
4
ca
bl
bl
8z
0
3
1 2
2 3
1 1
8
re
b7
ye
gr
0l
0l
ye
b7
7
4 1 19
2 4 21
2 5 317
4 5 34
4 7 3
4 8 265
8 6 71
3
4 3
2 6
1 4""".lines

    val expected = """Case #1:
-1
0
Case #2:
-1
0
0
Case #3:
3
55
-1""".lines

    process(input) { s => for (line<-s.lines)
      assert(line === expected.next())
    }
  }

  ignore("full small case") {
    val input = io.Source.fromFile("E-small-practice.in").getLines()
    val expected = io.Source.fromFile("e.small.out.ref").getLines()

    process(input) { s => for (line<-s.lines)
      assert(line === expected.next())
    }
  }

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

    process(input) { s => for (line<-s.lines)
      assert(line === expected.next())
    }
  }

}