結果
問題 | No.848 なかよし旅行 |
ユーザー | pekempey |
提出日時 | 2019-07-25 05:47:15 |
言語 | Kotlin (1.9.23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,586 bytes |
コンパイル時間 | 11,913 ms |
コンパイル使用メモリ | 445,992 KB |
実行使用メモリ | 160,068 KB |
最終ジャッジ日時 | 2024-04-30 21:09:22 |
合計ジャッジ時間 | 18,733 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
コンパイルメッセージ
Main.kt:33:10: warning: parameter 'args' is never used fun main(args: Array<String>) { ^
ソースコード
import java.util.PriorityQueue import java.util.Scanner 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 { if (d != other.d) return -d.compareTo(other.d) return u.compareTo(other.u) } } 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 } fun main(args: Array<String>) { val sc = Scanner(System.`in`) val N = sc.nextInt() val M = sc.nextInt() val P = sc.nextInt() - 1 val Q = sc.nextInt() - 1 val T = sc.nextLong() var g = Array(N, {mutableListOf<Edge>()}) repeat(M) { val u = sc.nextInt() - 1 val v = sc.nextInt() - 1 val w = sc.nextLong() g[u].add(Edge(v, w)) g[v].add(Edge(u, w)) } val d0 = dijkstra(g, 0) val dp = dijkstra(g, P) val dq = dijkstra(g, Q) 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])) } } } if (ans < 0L) { println(-1) } else { println(ans) } }