Rendezvous.scala

import scala.collection.SortedSet

object Rendezvous extends App {

  def toGraph(roads: Seq[(Int, Seq[Int])]): Map[Int, Set[(Int, Int)]] = {
    (for {
      (d, cs) <- roads
      (ci, cj) <- cs.init zip cs.tail
      a = ci min cj
      b = ci max cj
    } yield ((a, b), d)).groupBy(_._1).mapValues {
      _.map(_._2).min
    }.foldLeft(Map.empty[Int, Set[(Int, Int)]] withDefaultValue Set.empty) {
      case (g, ((a, b), d)) =>
        g + (a -> (g(a) + ((b, d)))) + (b -> (g(b) + ((a, d))))
    }
  }

  def minTime(friends: Seq[(Int, Int)], roads: Seq[(Int, Seq[Int])]): Option[Int] = {

    val graph = toGraph(roads)
    println(graph)

    @annotation.tailrec
    def dijkstra(dist: Map[Int, Int], visitable: SortedSet[(Int, Int)]): Map[Int, Int] = {
      if (visitable.isEmpty) dist
      else {
        val (t, u) = visitable.head
        val (dist1, visitable1) = ((dist + (u -> t), visitable.tail) /: graph(u)) {
          case ((dist, visitable), (v, d)) =>
            val alt = dist(u) + d
            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)
      }
    }

    val ans = (for {
      ((x, v), i) <- friends.zipWithIndex
      (c, d) <- dijkstra(Map.empty, SortedSet((0, x))).toSeq
    } yield (c, (i, d * v))).groupBy(_._1).mapValues(_.map(_._2).unzip).filter(_._2._1.toSet == (0 until friends.size).toSet).toSeq.map{ case (c, (fs, ts)) => (ts.sum, c)}

    println("--->" + ans)

    if (ans.isEmpty) None else Some(ans.min._1)


    //Some(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()
  }
}

RendezvousTest.scala

import org.scalatest._

import Rendezvous._

class RendezvousTest extends FunSuite with Matchers {

  test("toGraph") {
    assert(toGraph(Seq((1, Seq(2, 1, 2)))) === Map(1 -> Set((2, 1)), 2 -> Set((1, 1))))
  }

  test("sample #1") {
    assert(minTime(Seq((1, 1), (2, 2)), Seq((1, Seq(2, 1, 2)))) === Some(1))
  }

  test("sample #2") {
    assert(minTime(Seq((1,1), (5, 100)), Seq((1, Seq(3, 1, 2, 3)), (2, Seq(3, 4, 2, 5)))) === Some(3))
  }

  test("sample #3") {
    assert(minTime(Seq((1,1), (5, 5)), Seq((1, Seq(2, 1, 2)), (1, Seq(3, 3, 4, 5)))) === None)
  }

  ignore("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)
  }

  ignore("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.")
  }

}