promise.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.collection.immutable.IndexedSeq
import scala.io.StdIn

object Main extends App {
    Console.setIn(new FileInputStream("example.in"))
//
    Console.setIn(new FileInputStream("C-large-practice.in"))
    Console.setOut(new FileOutputStream("C-large-practice.out"))
//

    case class Friend(x:Int, v:Int)
    case class Road(d:Int, city:Array[Int])
    case class Cost(start:Int, end:Int, cost:Int)

    def solve(n:Int, friends:Array[Friend], roads:Array[Road]): Int = { // 도시 개수, 친구 목록, 도로 목록
//        println(s"n = $n")
//        println(s"friends = ${friends.mkString(", ")}")
//        println(s"roads = ${roads.mkString(", ")}")

        // 도시 -> 다음 도시, 비용
        val costs = roads.flatMap(road => {
            road.city.sliding(2).flatMap(x => {
                List(Cost(x(0), x(1), road.d), Cost(x(1), x(0), road.d))
            })
        })

        def dijkstra(start:Int, visited:List[Cost], result:Array[Int]):Array[Int] = { //출발점을 넣으면 각 노드로 까지의 시간

            // 출발점에서 갈수 있는 모든 노드를 넣습니다.
            val newCosts = costs.filter(x => x.start == start).map(x => x.copy(cost = x.cost + result(x.start)))
            val nexts = (newCosts ++ visited).filter(x => -1 == result(x.end))
            if (0 == nexts.length) {
                result
            } else {
                val near: Cost = nexts.minBy(_.cost)
                result(near.end) = near.cost
                dijkstra(near.end, nexts.toList, result)
            }
        }

        val costByCity = friends.map(friend => {
            val costList = Array.fill(n + 1)(-1)
            costList(friend.x) = 0
            dijkstra(friend.x, List(), costList).map(_ * friend.v)
        })

        val result = (1 to n).map(cityIdx => {
            costByCity.map(friendCost => friendCost(cityIdx)).filter(0 <= _)
        })

        if (result.exists(_.length == friends.length)) result.map(_.max).min else -1
        // 다엑스트라 -> 친구가 있는 도시에서 각 도시별 거리
        // 최소 시간이 걸리는 도시까지의 시간. (친구가 만날 수 없는 경우)
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { num =>
        val Array(n, p, m) = StdIn.readLine().split(" ").map(_.toInt)

        val friends: IndexedSeq[Friend] = for (idx <- 1 to p) yield {
            val Array(x, v) = StdIn.readLine().split(" ").map(x => x.toInt)
            Friend(x, v)
        }

        val roads: IndexedSeq[Road] = for (idx <- 1 to m) yield {
            val inputs: Array[Int] = StdIn.readLine().split(" ").map(x => x.toInt)
            val cities: Array[Int] = inputs.drop(2)
            Road(inputs.head, cities)
        }

        println(s"Case #$num: ${solve(n, friends.toArray, roads.toArray)}")
    }
}