GCampus.scala

import scala.collection.SortedSet

object GCampus extends App {

  case class Road(u: Int, v: Int, c: Int)

  def inefficientRoads(n: Int, roads: IndexedSeq[Road]): Set[Int] = {

    val graph = ((Map.empty[Int, Set[(Int, Int)]] withDefaultValue Set.empty) /: roads.zipWithIndex) {
      case (g, (Road(u, v, c), index)) =>
        g.updated(u, g(u) + ((v, index))).updated(v, g(v) + ((u, index)))
    }

    def efficientRoadsFrom(from: Int): Set[Int] = {
      @annotation.tailrec
      def dijkstra(dist: Map[Int, Int], prev: Map[Int, Set[Int]], visitable: SortedSet[(Int, Int)]): Map[Int, Set[Int]] =
        if (visitable.isEmpty) prev
        else {
          val u = visitable.head._2
          val (dist1, prev1, visitable1) = ((dist, prev, visitable.tail) /: graph(u)) {
            case ((dist, prev, visitable), (v, roadIndex)) =>
              val alt = dist(u) + roads(roadIndex).c
              if (!(dist contains v) || alt < dist(v))
                (dist + ((v -> alt)), prev + ((v -> Set(roadIndex))),
                  (if (dist contains v) visitable - ((dist(v), v)) else visitable) + ((alt, v)))
              else if (alt > dist(v)) (dist, prev, visitable)
              else (dist, prev + ((v -> (prev(v) + roadIndex))), visitable)
          }
          dijkstra(dist1, prev1, visitable1)
        }

      dijkstra(Map(from -> 0), Map(from -> Set.empty), SortedSet((0, from))).values.reduce(_ ++ _)
    }

    SortedSet.empty[Int] ++ (0 until roads.size) -- (0 until n map efficientRoadsFrom reduce (_ ++ _))
  }

  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) = readInts()
      val roads = IndexedSeq.fill(m) {
        val Array(u, v, c) = readInts()
        Road(u, v, c)
      }
      lineOut(s"Case #$i:")
      inefficientRoads(n, roads) foreach (n => lineOut(n.toString))
    }

  val filename = "C-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()
  }
}

GCampusTest.scala

import org.scalatest._

import GCampus._

class GCampusTest extends FunSuite with Matchers {

  test("sample #1") {
    assert(inefficientRoads(3, IndexedSeq(Road(0, 1, 10), Road(1, 2, 3), Road(2, 0, 3))) === Set(0))
  }

  test("sample #2") {
    assert(inefficientRoads(3, IndexedSeq(Road(0, 1, 10), Road(1, 2, 3), Road(2, 1, 3))) === Set())
  }

  test("sample case") {
    val input = """2
3 3
0 1 10
1 2 3
2 0 3
3 3
0 1 10
1 2 3
2 1 3""".lines

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

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

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("C-large-practice.in").getLines()
    val expected = io.Source.fromFile("C-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.")
  }

}