gCampus (https://code.google.com/codejam/contest/4284486/dashboard#s=p2)

Main.scala

object Main extends App {

  import scala.io._
  import java.io._

  def parseLine(s: String) = s.split(' ').map(_.trim).filter(_.nonEmpty).map(_.toInt).toList

  // val filename = "example.in"
  // val filename = "C-small-practice.in"
  val filename = "C-large-practice.in"

  val lines = Source.fromFile(filename)
    .getLines
    .toList

  val nrOfCases = parseLine(lines.head).head

  val pw = new PrintWriter(new File(filename.replace(".in", ".out")))

  (1 to nrOfCases).foldLeft(lines.tail) { (linesLeft, i) =>
      val List(n, m) = parseLine(linesLeft.head)
      val (_paths, remains) = linesLeft.tail.splitAt(m)
      val paths =
        _paths
          .map(parseLine)
          .map { case List(from, to, dist) => (from, to, dist) }

      val solution = Solver.solve(n, m, paths)
      pw.println(s"Case #$i:")
      pw.println(solution.mkString("\n"))
      remains
  }

  pw.close()

}

Solver.scala

object Solver {

  type Office = Int
  type Distance = Int
  type Road = Int
  type Path = (Office, Office)

  val MaxCi = 1000000
  val MaxN = 100

  val InfiniteDist = MaxCi * MaxN

  def solve(n: Int, m: Int,
            roads: List[(Office, Office, Distance)]): List[Road] = {

    val shortestDirectPaths: Map[Path, (Distance, List[Road])] =
      roads
        .zipWithIndex
        .collect {
          case ((from, to, dist), idx) if from != to =>
            List(
              (from, to) -> (dist, idx),
              (to, from) -> (dist, idx)
            )
        }
        .flatten
        .groupBy(_._1)
        .mapValues { v =>
          val d2 = v.map(_._2).sortBy(_._1)
          val min = d2.head._1
          val roads = d2.takeWhile(_._1 == min).map(_._2)
          (min, roads)
        }

    val initialPaths: Map[Path, (Distance, Boolean)] =
      shortestDirectPaths
        .map {
          case (path, (dist, _)) => path -> (dist, true)
        }
        .withDefaultValue((InfiniteDist, false))


    import cats.syntax.apply._
    import cats.std.list._

    val offices = (0 until n).toList
    val shortestPaths =
      (offices |@| offices |@| offices)
        .tupled
        .foldLeft(initialPaths) { case (paths, (k, i, j)) =>
          val (distItoJ, _) = paths(i -> j)
          val distViaK = paths(i -> k)._1 + paths(k -> j)._1

          if (distViaK < distItoJ)
            paths.updated(i -> j, (distViaK, false))
          else
            paths
        }

    val usedRoads: Set[Road] =
      shortestPaths
        .toList
        .collect {
          case (path, (_, isDirect)) if isDirect =>
            shortestDirectPaths(path)._2
        }
        .flatten
        .toSet

    (0 until m).filterNot(usedRoads).toList
  }
}