Submission #2120189


Source Code Expand

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

val DEBUG = false

val P = 1000000007L

//data class FiniteField(val x: Long) {
//  val p = 1000000007L
//  operator fun plus(o: FiniteField) = FiniteField((x + o.x) % p)
//  operator fun minus(o: FiniteField) = FiniteField((x + p - o.x) % p)
//  operator fun times(o: FiniteField) = FiniteField((x * o.x) % p)
//}

data class Edge(val from: Int, val to: Int, val cost: Long)

data class State(val v: Int, val cost: Long)

fun compareState(s1: State, s2: State): Int {
  if (s1.cost > s2.cost) return 1
  if (s1.cost < s2.cost) return -1
  return 0
}

fun readInts(s: String): List<Int> {
  val values = mutableListOf<Int>()
  var start = 0
  for (i in 0 until s.length) {
    if (s[i] == ' ') {
      values.add(s.substring(start, i).toInt())
      start = i + 1
    }
  }
  values.add(s.substring(start).toInt())
  return values
}

fun main(args: Array<String>) {
  val inputReader = BufferedReader(InputStreamReader(System.`in`))
  val (n, m) = inputReader.readLine()!!.split(" ").map(String::toInt)
  val (sRaw, tRaw) = inputReader.readLine()!!.split(" ").map(String::toInt)
  val s = sRaw - 1
  val t = tRaw - 1
  val graph = Array(n, { mutableListOf<Edge>() })
  repeat(m) {
    val line = inputReader.readLine()!!
    val (uRaw, vRaw, dInt) = readInts(line)
    val u = uRaw - 1
    val v = vRaw - 1
    val d = dInt.toLong()
    graph[u].add(Edge(u, v, d))
    graph[v].add(Edge(v, u, d))
  }

  // Dijkstra from s
  val pq = PriorityQueue<State>(11, { s1: State, s2: State -> compareState(s1, s2) })
  val dist = LongArray(n, { -1L })
  pq.add(State(s, 0L))
  while (pq.isNotEmpty()) {
    val state = pq.poll()!!
    if (dist[state.v] >= 0) continue
    dist[state.v] = state.cost
    for (e in graph[state.v]) {
      if (dist[e.to] < 0) {
        pq.add(State(e.to, state.cost + e.cost))
      }
    }
  }
  if (DEBUG) println("dist: ${dist.toList()}")

  val sGraph = Array(n, { mutableListOf<Int>() })
  val tGraph = Array(n, { mutableListOf<Int>() })

  val stack = Stack<Int>()
  stack.push(t)
  val visited = BooleanArray(n)
  while (stack.isNotEmpty()) {
    val v = stack.pop()!!
    if (visited[v]) continue
    visited[v] = true
    if (DEBUG) println("v: $v")
    for (e in graph[v]) {
      if (dist[v] == dist[e.to] + e.cost) {
        tGraph[v].add(e.to)
        sGraph[e.to].add(v)
        stack.push(e.to)
      }
    }
  }
//  for (v in 0 until n) {
//    for (e in graph[v]) {
//      if (dist[v] + e.cost == dist[e.to]) {
//        tGraph[e.to].add(v)
//        sGraph[v].add(e.to)
//      }
//    }
//  }
  if (DEBUG) println("sGraph: ${sGraph.toList()}")
  if (DEBUG) println("tGraph: ${tGraph.toList()}")

//  val sCount = Array(n, { FiniteField(0) })
//  sCount[s] = FiniteField(1)
//  val sSorted = dist.withIndex().sortedBy { it.value }.map { it.index }
//  fillCount(s, sGraph, sSorted, sCount)
//  if (DEBUG) println("sCount: ${sCount.toList()}")
//
//  val tCount = Array(n, { FiniteField(0) })
//  tCount[t] = FiniteField(1)
//  val tSorted = sSorted.reversed()
//  fillCount(t, tGraph, tSorted, tCount)
//  if (DEBUG) println("tCount: ${tCount.toList()}")
//
//  var ans = sCount[t] * tCount[s]
//  if (DEBUG) println("ans STEP 1: $ans")
//  val totalDist = dist[t]
//  // Meet on vertex
//  for (v in 0 until n) {
//    if (dist[v] * 2 == totalDist) {
//      ans -= sCount[v] * sCount[v] * tCount[v] * tCount[v]
//    }
//  }
//  if (DEBUG) println("ans STEP 2: $ans")
//
//  // Meet on edge
//  for (v in 0 until n) {
//    for (e in graph[v]) {
//      if (dist[v] + e.cost == dist[e.to] && dist[v] * 2 < totalDist && dist[e.to] * 2 > totalDist) {
//        ans -= sCount[v] * sCount[v] * tCount[e.to] * tCount[e.to]
//      }
//    }
//  }
//  if (DEBUG) println("ans STEP 3: $ans")

  val sCount = LongArray(n, { 0L })
  sCount[s] = 1L
  val sSorted = dist.withIndex().sortedBy { it.value }.map { it.index }
  fillCount(s, sGraph, sSorted, sCount)
  if (DEBUG) println("sCount: ${sCount.toList()}")

  val tCount = LongArray(n, { 0L })
  tCount[t] = 1L
  val tSorted = sSorted.reversed()
  fillCount(t, tGraph, tSorted, tCount)
  if (DEBUG) println("tCount: ${tCount.toList()}")

  var ans = sCount[t] * tCount[s]
  if (DEBUG) println("ans STEP 1: $ans")
  val totalDist = dist[t]
  // Meet on vertex
  for (v in 0 until n) {
    if (dist[v] * 2 == totalDist) {
      val f1 = sCount[v] * sCount[v] % P
      val f2 = tCount[v] * tCount[v] % P
      val delta = f1 * f2 % P
      ans = (ans + P - delta) % P
    }
  }
  if (DEBUG) println("ans STEP 2: $ans")

  // Meet on edge
  for (v in 0 until n) {
    for (e in graph[v]) {
      if (dist[v] + e.cost == dist[e.to] && dist[v] * 2 < totalDist && dist[e.to] * 2 > totalDist) {
        val f1 = sCount[v] * sCount[v] % P
        val f2 = tCount[e.to] * tCount[e.to] % P
        val delta = f1 * f2 % P
        ans = (ans + P - delta) % P
      }
    }
  }
  if (DEBUG) println("ans STEP 3: $ans")

  println(ans)
}

fun fillCount(r: Int, graph: Array<MutableList<Int>>, tSorted: List<Int>, count: LongArray) {
  for (v in tSorted) {
    for (u in graph[v]) {
      count[u] = (count[u] + count[v]) % P
    }
  }
}

Submission Info

Submission Time
Task E - Avoiding Collision
User ymatsux
Language Kotlin (1.0.0)
Score 700
Code Size 5377 Byte
Status AC
Exec Time 1773 ms
Memory 159712 KB

Compile Error

Main.kt:177:15: warning: parameter 'r' is never used
fun fillCount(r: Int, graph: Array<MutableList<Int>>, tSorted: List<Int>, count: LongArray) {
              ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 22
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt
Case Name Status Exec Time Memory
01.txt AC 1264 ms 141104 KB
02.txt AC 1173 ms 145940 KB
03.txt AC 1719 ms 154064 KB
04.txt AC 1722 ms 153272 KB
05.txt AC 1253 ms 140500 KB
06.txt AC 1597 ms 148120 KB
07.txt AC 1681 ms 157304 KB
08.txt AC 1295 ms 146628 KB
09.txt AC 1693 ms 158084 KB
10.txt AC 1722 ms 155704 KB
11.txt AC 1686 ms 155132 KB
12.txt AC 1682 ms 159712 KB
13.txt AC 1773 ms 157408 KB
14.txt AC 1756 ms 157300 KB
15.txt AC 1745 ms 157320 KB
16.txt AC 1706 ms 153564 KB
17.txt AC 1685 ms 154024 KB
18.txt AC 1728 ms 155860 KB
sample01.txt AC 213 ms 35780 KB
sample02.txt AC 213 ms 35912 KB
sample03.txt AC 214 ms 31936 KB
sample04.txt AC 214 ms 37676 KB