Submission #1518226

---

Source Code Expand

import java.util.Scanner

import scala.collection.mutable

object Main {
  def solve(sc: => Scanner): Unit = {
    val N, M = sc.nextInt
    val S, T = sc.nextInt - 1
    val mapping = Array.fill[List[Int]](N)(List())
    for (i <- 0 until M) {
      val x, y = sc.nextInt - 1
      mapping(x).+:=(y)
      mapping(y).+:=(x)
    }
    System.gc()
    val len1 = Array.fill[Int](N)(Int.MaxValue / 6)
    len1(S) = 0
    val que1 = mutable.Queue[Int](S)
    while (que1.size != 0) {
      val now = que1.dequeue()
      for (next <- mapping(now)) {
        if (len1(next) > len1(now) + 1 && len1(now) + 1 <= len1(T)) {
          len1(next) = len1(now) + 1
          que1.enqueue(next)
        }
      }
    }
    System.gc()
    val lenST = len1(T) - 2
    val len2 = Array.fill[Int](N)(Int.MaxValue / 6)
    len2(T) = 0
    val que2 = mutable.Queue[Int](T)
    while (que2.size != 0) {
      val now = que2.dequeue()
      for (next <- mapping(now)) {
        if (len2(next) > len2(now) + 1 && len2(now) + 1 <= lenST) {
          len2(next) = len2(now) + 1
          que2.enqueue(next)
        }
      }
    }
    System.gc()
    val list1g = len1.filter(x => x <= lenST).groupBy(x => x)
    val list2g = len2.filter(x => x <= lenST).groupBy(x => x)
    System.gc()
    var ans = 0
    for (i <- 0 to lenST) {
      val j = lenST - i
      ans += list1g(i).length * list2g(j).length
    }
    println(ans)
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

Submission Info

Judge Result