SPOJ #15

gistfile1.scala

package com.algoclass.dij

import collection.immutable.IndexedSeq


object Main {
  def readCityBlock(id: Int) = {
    val cityName = readLine()
    val neighbours = readLine().toInt
    val fromVertex = new Vertex(cityName, id)
    val stuffToAddToMap: IndexedSeq[(Vertex, (Int, Int))] =
      for (i <- 1 to neighbours; Array(indexOfToVertex, cost) = readLine().split(" "))
      yield (fromVertex -> (indexOfToVertex.toInt, cost.toInt))

    (stuffToAddToMap, fromVertex)
  }

  def asGraph(cities: IndexedSeq[(IndexedSeq[(Vertex, (Int, Int))], Vertex)], vertices: List[Vertex]) = {
    val verticesMap = vertices.map { v => (v.id, v) }.toMap
    cities.foldLeft(Map[Vertex, List[(Vertex, Int)]]()) {
      case ((graph), (addToGraph, _)) => {
        addToGraph.foldLeft(graph) {
          (map, pair) => {
            val existingEntry = map.get(pair._1)
            if (existingEntry.nonEmpty)
              map + (pair._1 -> (map(pair._1) ++ List((verticesMap(pair._2._1), pair._2._2))))
            else
              map + (pair._1 -> List((verticesMap(pair._2._1), pair._2._2)))
          }
        }
      }
    }
  }

  def readPath(): (String, String) = {
    val line = readLine()
    val (city1 :: city2 :: _) = """\s""".r.split(line).toList
    (city1, city2)
  }


  def asVertices(cities: IndexedSeq[(IndexedSeq[(Vertex, (Int, Int))], Vertex)]) = {
    cities.foldLeft(List[Vertex]()) { case ((vertices), (_, newVertex)) => vertices ++ List(newVertex) }
  }

  def asPaths(paths: Seq[(String, String)], vertices: List[Vertex]) = {
    val verticesMap = vertices.map { v => (v.name, v) }.toMap
    paths.map { case (city1, city2) => (verticesMap(city1), verticesMap(city2)) }
  }

  def main(args: Array[String]) {
    val numberOfTests = readLine().toInt
    val numberOfCities = readLine().toInt

    val cities = for (i <- 1 to numberOfCities) yield readCityBlock(i)

    val numberOfPaths = readLine().toInt
    val paths = for (i <- 1 to numberOfPaths) yield readPath()

    val vertices = asVertices(cities)
    val graph = asGraph(cities, vertices)
    val finalPaths = asPaths(paths, vertices)

    finalPaths.foreach(startEnd => go(startEnd, graph, vertices))
  }

  def go(startEnd: (Vertex, Vertex), graph: Map[Vertex, List[(Vertex, Int)]], vertices: List[Vertex]) {
    val visited = Set(startEnd._1)
    val leastCost = shortestPathCost(startEnd, visited, graph, Map[Vertex, Int](startEnd._1 -> 0))
    println(leastCost)
  }

  def shortestPathCost(startEnd: (Vertex, Vertex), visited: Set[Vertex],
                       graph: Map[Vertex, scala.List[(Vertex, Int)]],
                       scores: Map[Vertex, Int]): Int = {
    val map = visited.flatMap(v => graph(v).map { t => (v, t) })
    val allPossibilities = map.filter { entry => !visited.contains(entry._2._1)}
    val (fromVertex, (toVertex, cost)) = findShortest(allPossibilities)
    val updatedScores = scores + (toVertex -> (scores(fromVertex) + cost))

    if (toVertex == startEnd._2) updatedScores(toVertex) else shortestPathCost(startEnd, visited + toVertex, graph, updatedScores)
  }

  def findShortest(allPossibilities: Set[(Vertex, (Vertex, Int))]) = {
    allPossibilities.reduceLeft {
      (leastPossibilitySoFar, possibility) =>
        if (possibility._2._2 <= leastPossibilitySoFar._2._2) possibility else leastPossibilitySoFar
    }
  }

  case class Vertex(name: String, id: Int)
}