結果

問題 No.848 なかよし旅行
ユーザー Haar
提出日時 2020-06-19 01:57:51
言語 Nim
(2.2.0)
結果
AC  
実行時間 250 ms / 2,000 ms
コード長 1,782 bytes
コンパイル時間 6,189 ms
コンパイル使用メモリ 69,708 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2024-11-08 01:16:58
合計ジャッジ時間 7,673 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
/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