結果
問題 | No.848 なかよし旅行 |
ユーザー | pekempey |
提出日時 | 2019-07-25 07:26:06 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 829 ms / 2,000 ms |
コード長 | 2,244 bytes |
コンパイル時間 | 13,614 ms |
コンパイル使用メモリ | 454,280 KB |
実行使用メモリ | 99,176 KB |
最終ジャッジ日時 | 2024-04-25 14:02:51 |
合計ジャッジ時間 | 27,477 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 829 ms
99,176 KB |
testcase_01 | AC | 290 ms
60,312 KB |
testcase_02 | AC | 292 ms
60,400 KB |
testcase_03 | AC | 294 ms
60,448 KB |
testcase_04 | AC | 292 ms
60,476 KB |
testcase_05 | AC | 288 ms
60,340 KB |
testcase_06 | AC | 298 ms
60,372 KB |
testcase_07 | AC | 287 ms
60,484 KB |
testcase_08 | AC | 304 ms
60,468 KB |
testcase_09 | AC | 317 ms
60,604 KB |
testcase_10 | AC | 312 ms
60,512 KB |
testcase_11 | AC | 491 ms
66,264 KB |
testcase_12 | AC | 473 ms
67,320 KB |
testcase_13 | AC | 513 ms
69,828 KB |
testcase_14 | AC | 416 ms
60,800 KB |
testcase_15 | AC | 525 ms
69,904 KB |
testcase_16 | AC | 585 ms
70,864 KB |
testcase_17 | AC | 496 ms
68,704 KB |
testcase_18 | AC | 497 ms
65,468 KB |
testcase_19 | AC | 454 ms
65,728 KB |
testcase_20 | AC | 360 ms
60,748 KB |
testcase_21 | AC | 492 ms
68,568 KB |
testcase_22 | AC | 474 ms
71,128 KB |
testcase_23 | AC | 369 ms
60,632 KB |
testcase_24 | AC | 284 ms
60,412 KB |
testcase_25 | AC | 581 ms
72,816 KB |
testcase_26 | AC | 279 ms
60,412 KB |
testcase_27 | AC | 275 ms
60,228 KB |
testcase_28 | AC | 277 ms
60,316 KB |
testcase_29 | AC | 295 ms
60,468 KB |
コンパイルメッセージ
Main.kt:61:16: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. while ('0'.toByte() > peek()) next() ^ Main.kt:62:16: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. while ('0'.toByte() <= peek()) { ^ Main.kt:63:38: warning: 'toLong(): Long' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. ans = ans * 10 + (peek() - '0'.toLong()) ^ Main.kt:74:10: warning: parameter 'args' is never used fun main(args: Array<String>) { ^
ソースコード
import java.util.PriorityQueue import java.util.Scanner import java.io.BufferedReader import java.io.InputStreamReader data class Edge(val v: Int, val w: Long) val INF = 1e18.toLong() fun dijkstra(g: Array<MutableList<Edge>>, s: Int): Array<Long> { data class State(val d: Long, val u: Int) : Comparable<State> { override operator fun compareTo(other: State): Int { return d.compareTo(other.d) } } var q: PriorityQueue<State> = PriorityQueue() val n = g.size var dist = Array(n, {INF}) dist[s] = 0 q.add(State(0, s)) while (!q.isEmpty()) { val (d, u) = q.remove() if (d > dist[u]) continue for (e in g[u]) { if (dist[e.v] > dist[u] + e.w) { dist[e.v] = dist[u] + e.w q.add(State(dist[e.v], e.v)) } } } return dist } class Reader { var buf: ByteArray = ByteArray(5000000) var k: Int = 0 var n: Int = 0 init { check() } private fun check() { if (k == n) { n = System.`in`.read(buf) k = 0 } } private fun peek(): Byte { return buf[k] } private fun next() { k++ check() } fun long(): Long { var ans: Long = 0 while ('0'.toByte() > peek()) next() while ('0'.toByte() <= peek()) { ans = ans * 10 + (peek() - '0'.toLong()) next() } return ans } fun int(): Int { return long().toInt() } } fun main(args: Array<String>) { var r = Reader() val N = r.int() val M = r.int() val P = r.int() - 1 val Q = r.int() - 1 val T = r.long() var g = Array(N, {mutableListOf<Edge>()}) repeat(M) { val u = r.int() - 1 val v = r.int() - 1 val w = r.long() g[u].add(Edge(v, w)) g[v].add(Edge(u, w)) } val start = System.currentTimeMillis() val d0 = dijkstra(g, 0) val dp = dijkstra(g, P) val dq = dijkstra(g, Q) val end = System.currentTimeMillis() var ans = -INF if (dp[0] + dp[Q] + dq[0] <= T) { ans = T } for (i in 0..N-1) { for (j in 0..N-1) { if (d0[i] + d0[j] + maxOf(dp[i] + dp[j], dq[i] + dq[j]) <= T) { ans = maxOf(ans, T - maxOf(dp[i] + dp[j], dq[i] + dq[j])) } } } System.err.println(end - start) if (ans < 0L) { println(-1) } else { println(ans) } }