結果

問題 No.848 なかよし旅行
ユーザー HaarHaar
提出日時 2020-06-19 01:57:51
言語 Nim
(2.0.2)
結果
AC  
実行時間 237 ms / 2,000 ms
コード長 1,782 bytes
コンパイル時間 4,194 ms
コンパイル使用メモリ 69,704 KB
実行使用メモリ 14,464 KB
最終ジャッジ日時 2024-04-25 14:17:27
合計ジャッジ時間 6,421 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 237 ms
14,464 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 4 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 56 ms
6,940 KB
testcase_12 AC 74 ms
6,944 KB
testcase_13 AC 98 ms
7,808 KB
testcase_14 AC 47 ms
6,940 KB
testcase_15 AC 87 ms
7,808 KB
testcase_16 AC 142 ms
11,520 KB
testcase_17 AC 95 ms
9,856 KB
testcase_18 AC 55 ms
6,940 KB
testcase_19 AC 51 ms
6,940 KB
testcase_20 AC 44 ms
6,944 KB
testcase_21 AC 110 ms
10,112 KB
testcase_22 AC 94 ms
11,008 KB
testcase_23 AC 72 ms
6,940 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 177 ms
11,392 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(7, 8) Warning: imported and not used: 'strformat' [UnusedImport]

ソースコード

diff # 

import strutils
import macros
import typetraits
import options
import heapqueue
import sequtils
import strformat


type
  Edge*[T] = object
    to*: int
    cost*: T
  
  Graph*[T] = seq[seq[Edge[T]]]

proc make*[T](t: typedesc[Graph[T]], size: int): Graph[T] {.noSideEffect.} =
  return Graph[T](newSeq[seq[Edge[T]]](size))

proc add_edge*[T](g: var Graph[T], s, t: int, c: T) = g[s].add(Edge[T](to: t, cost: c))

proc dijkstra*[T](g: Graph[T], s: int): seq[Option[T]] =
  let N = g.len
  var dist = newSeq[Option[T]](N)
  var check = newSeq[bool](N)
  var heap = initHeapQueue[(T, int)]()

  dist[s] = some(T(0))
  heap.push((T(0), s))

  while heap.len != 0:
    let (d, i) = heap.pop

    if check[i]: continue
    check[i] = true

    for e in g[i]:
      if dist[e.to].isNone:
        dist[e.to] = some(d + e.cost)
        heap.push((dist[e.to].get, e.to))

      elif dist[i].get + e.cost < dist[e.to].get:
        dist[e.to] = some(dist[i].get + e.cost)
        heap.push((dist[e.to].get, e.to))

  return dist





let res = stdin.readline.split.mapIt(it.parseInt)
let N = res[0]
let M = res[1]
let P = res[2] - 1
let Q = res[3] - 1
let T = res[4]

var g = Graph[int64].make(N)

for i in 0 ..< M:
  let res = stdin.readline.split.mapIt(it.parseInt)
  let a = res[0] - 1
  let b = res[1] - 1
  let c = res[2]

  g.add_edge(a, b, c)
  g.add_edge(b, a, c)




let dist0 = g.dijkstra(0)
let distp = g.dijkstra(P)
let distq = g.dijkstra(Q)

var ans: int64 = -1

if dist0[P].get + distp[Q].get + dist0[Q].get <= T:
  ans = max(ans, T)

for i in 0 ..< N:
  for j in 0 ..< N:
    if dist0[i].get + max(distp[i].get + distp[j].get, distq[i].get + distq[j].get) + dist0[j].get <= T:
      ans = max(ans, T - max(distp[i].get + distp[j].get, distq[i].get + distq[j].get))

echo ans
0