import scala.collection.mutable.PriorityQueue import scala.collection.mutable.ListBuffer import scala.collection.mutable.HashSet object Main { val sc = new java.util.Scanner(System.in) def readInts(): Array[Int] = sc.nextLine.split(' ').map(_.toInt) def Ord = new Ordering[(Int, Int, Int)] { def compare(a: (Int, Int, Int), b: (Int, Int, Int)): Int = b._3.compare(a._3) } def calc(n: Int, s: Int, g: Int, nodes: ListBuffer[(Int, Int, Int)]) { val q = new PriorityQueue[(Int, Int, Int)]()(Ord) // (from, to, cost) q.enqueue((0, g, 0)) val pathcost = Array.fill(n)(Int.MaxValue) val prev = Array.fill(n)(new ListBuffer[Int]) while (!q.isEmpty) { val (from, to, cost) = q.dequeue if (cost == pathcost(to)) { prev(to).append(from) } else if (cost < pathcost(to)) { pathcost(to) = cost prev(to).append(from) // println("visit:", to, "cost:", cost) for ((a, b, c) <- nodes) { if (a == to) q.enqueue((to, b, cost + c)) else if (b == to) q.enqueue((to, a, cost + c)) } } } // 経路復元 val path = new ListBuffer[Int] path.append(s) while (path.last != g) { path.append(prev(path.last).min) } println(path.mkString(" ")) } def main(args: Array[String]) { val Array(n, m, s, g) = readInts() val nodes = new ListBuffer[(Int, Int, Int)] for (i <- 0 to m-1) { val Array(a, b, c) = readInts() nodes.append((a, b, c)) } calc(n, s, g, nodes) } }