結果
| 問題 | No.2604 Initial Motion |
| ユーザー |
👑  seekworser
|
| 提出日時 | 2023-12-29 20:30:20 |
| 言語 | Nim (2.0.2) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 21,957 bytes |
| コンパイル時間 | 6,474 ms |
| コンパイル使用メモリ | 95,548 KB |
| 実行使用メモリ | 733,884 KB |
| 最終ジャッジ日時 | 2024-09-27 16:20:39 |
| 合計ジャッジ時間 | 13,539 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,756 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,940 KB |
| testcase_03 | AC | 140 ms
28,728 KB |
| testcase_04 | AC | 146 ms
28,752 KB |
| testcase_05 | AC | 133 ms
28,764 KB |
| testcase_06 | AC | 139 ms
28,856 KB |
| testcase_07 | AC | 145 ms
28,824 KB |
| testcase_08 | AC | 150 ms
28,760 KB |
| testcase_09 | AC | 140 ms
28,728 KB |
| testcase_10 | AC | 140 ms
28,768 KB |
| testcase_11 | AC | 143 ms
28,844 KB |
| testcase_12 | AC | 141 ms
28,664 KB |
| testcase_13 | MLE | - |
| 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 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
ソースコード
import macros
macro Please(x): untyped = nnkStmtList.newTree()
Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
import macros
# {.checks: off.}
ImportExpand "cplib/tmpl/citrus.nim" <=== "when not declared CPLIB_TMPL_CITRUS:\n const CPLIB_TMPL_CITRUS* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import os\n import algorithm\n import sequtils\n import tables\n import macros\n import std/math\n import sets\n import strutils\n import strformat\n import sugar\n import streams\n import deques\n import bitops\n import heapqueue\n const MODINT998244353* = 998244353\n const MODINT1000000007* = 1000000007\n const INF* = 100100111\n const INFL* = int(3300300300300300491)\n type double* = float64\n let readNext = iterator(getsChar: bool = false): string {.closure.} =\n while true:\n var si: string\n try: si = stdin.readLine\n except EOFError: yield \"\"\n for s in si.split:\n if getsChar:\n for i in 0..<s.len(): yield s[i..i]\n else:\n yield s\n proc input*(t: typedesc[string]): string = readNext()\n proc input*(t: typedesc[char]): char = readNext(true)[0]\n proc input*(t: typedesc[int]): int = readNext().parseInt\n proc input*(t: typedesc[float]): float = readNext().parseFloat\n macro input*(t: typedesc, n: varargs[int]): untyped =\n var repStr = \"\"\n for arg in n:\n repStr &= &\"({arg.repr}).newSeqWith \"\n parseExpr(&\"{repStr}input({t})\")\n macro input*(ts: varargs[auto]): untyped =\n var tupStr = \"\"\n for t in ts:\n tupStr &= &\"input({t.repr}),\"\n parseExpr(&\"({tupStr})\")\n macro input*(n: int, ts: varargs[auto]): untyped =\n for typ in ts:\n if typ.typeKind != ntyAnything:\n error(\"Expected typedesc, got \" & typ.repr, typ)\n parseExpr(&\"({n.repr}).newSeqWith input({ts.repr})\")\n proc `fmtprint`*(x: int or string or char): string = return $x\n proc `fmtprint`*(x: float or float32 or\n float64): string = return &\"{x:.16f}\"\n proc `fmtprint`*[T](x: seq[T] or Deque[T] or HashSet[T] or set[\n T]): string = return x.toSeq.join(\" \")\n proc `fmtprint`*[T, N](x: array[T, N]): string = return x.toSeq.join(\" \")\n proc `fmtprint`*[T](x: HeapQueue[T]): string =\n var q = x\n while q.len != 0:\n result &= &\"{q.pop()}\"\n if q.len != 0: result &= \" \"\n proc `fmtprint`*[T](x: CountTable[T]): string =\n result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n proc `fmtprint`*[K, V](x: Table[K, V]): string =\n result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool],\n args: varargs[string, `fmtprint`]) =\n for i in 0..<len(args):\n prop.f.write(&\"{args[i]}\")\n if i != len(args) - 1: prop.f.write(prop.sepc) else: prop.f.write(prop.endc)\n if prop.flush: prop.f.flushFile()\n proc print*(args: varargs[string, `fmtprint`]) = print((f: stdout,\n sepc: \" \", endc: \"\\n\", flush: false), args)\n proc inner_debug*(x: auto) = print((f: stderr, sepc: \"\", endc: \"\",\n flush: true), x)\n const LOCAL_DEBUG{.booldefine.} = false\n macro debug*(n: varargs[typed]): untyped =\n when LOCAL_DEBUG:\n result = newNimNode(nnkStmtList, n)\n for i in 0..n.len-1:\n if n[i].kind == nnkStrLit:\n result.add(newCall(\"inner_debug\", n[i]))\n result.add(newCall(\"inner_debug\", newStrLitNode(\": \")))\n result.add(newCall(\"inner_debug\", n[i]))\n else:\n result.add(newCall(\"inner_debug\", toStrLit(n[i])))\n result.add(newCall(\"inner_debug\", newStrLitNode(\": \")))\n result.add(newCall(\"inner_debug\", n[i]))\n if i != n.len-1:\n result.add(newCall(\"inner_debug\", newStrLitNode(\", \")))\n else:\n result.add(newCall(\"inner_debug\", newStrLitNode(\"\\n\")))\n else:\n return quote do:\n discard\n proc `%`*(x: SomeInteger, y: SomeInteger): int = (((x mod y) + y) mod y)\n proc `//`*(x: int, y: int): int = ((x - (x%y)) div y)\n proc `^`*(x: int, y: int): int = x xor y\n proc `&`*(x: int, y: int): int = x and y\n proc `|`*(x: int, y: int): int = x or y\n proc `>>`*(x: int, y: int): int = x shr y\n proc `<<`*(x: int, y: int): int = x shl y\n proc `%=`*(x: var SomeInteger or int64, y: SomeInteger or\n int64): void = x = x % y\n proc `//=`*(x: var int, y: int): void = x = x // y\n proc `^=`*(x: var int, y: int): void = x = x ^ y\n proc `&=`*(x: var int, y: int): void = x = x & y\n proc `|=`*(x: var int, y: int): void = x = x | y\n proc `>>=`*(x: var int, y: int): void = x = x >> y\n proc `<<=`*(x: var int, y: int): void = x = x << y\n proc `[]`*(x: int, n: int): bool = (x and (1 shl n)) != 0\n\n proc pow*(a, n: int, m = INFL): int =\n var\n rev = 1\n a = a\n n = n\n while n > 0:\n if n % 2 != 0: rev = (rev * a) mod m\n if n > 1: a = (a * a) mod m\n n >>= 1\n return rev\n proc sqrt*(x: int): int =\n assert(x >= 0)\n result = int(sqrt(float64(x)))\n while result * result > x: result -= 1\n while (result+1) * (result+1) <= x: result += 1\n proc chmax*[T](x: var T, y: T): bool = (if x < y: (x = y; return true;\n ) return false)\n proc chmin*[T](x: var T, y: T): bool = (if x > y: (x = y; return true;\n ) return false)\n proc `max=`*[T](x: var T, y: T) = x = max(x, y)\n proc `min=`*[T](x: var T, y: T) = x = min(x, y)\n proc at*(x: char, a = '0'): int = int(x) - int(a)\n converter tofloat*(n: int): float = float(n)\n iterator rangeiter*(start: int, ends: int, step: int): int =\n var i = start\n if step < 0:\n while i > ends:\n yield i\n i += step\n elif step > 0:\n while i < ends:\n yield i\n i += step\n iterator rangeiter*(ends: int): int = (for i in 0..<ends: yield i)\n iterator rangeiter*(start: int, ends: int): int = (for i in\n start..<ends: yield i)\n proc Yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n proc No*(b: bool = true): void = Yes(not b)\n proc YES_upper*(b: bool = true): void = print(if b: \"YES\" else: \"NO\")\n proc NO_upper*(b: bool = true): void = Yes_upper(not b)\n const DXY* = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n const DDXY* = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0),\n (-1, 1)]\n macro exit*(statement: untyped): untyped =\n quote do:\n `statement`\n quit()\n proc vector*[T](d1, : int, default: T = T(0)): seq[T] = newSeqWith(d1, default)\n proc vv*[T](d1, d2: int, default: T = T(0)): seq[seq[T]] = newSeqWith(d1,\n newSeqWith(d2, default))\n proc vvv*[T](d1, d2, d3: int, default: T = T(0)): seq[seq[seq[\n T]]] = newSeqWith(d1, newSeqWith(d2, newSeqWith(d3, default)))\n proc vvvv*[T](d1, d2, d3, d4: int, default: T = T(0)): seq[seq[seq[seq[\n T]]]] = newSeqWith(d1, newSeqWith(d2, newSeqWith(d3, newSeqWith(d4, default))))\n proc vvvvv*[T](d1, d2, d3, d4, d5: int, default: T = T(0)): seq[seq[seq[seq[\n seq[T]]]]] = newSeqWith(d1, newSeqWith(d2, newSeqWith(d3,\n newSeqWith(d4, newSeqWith(d5, default)))))\n proc vvvvvv*[T](d1, d2, d3, d4, d5, d6: int, default: T = T(0)): seq[seq[\n seq[seq[seq[seq[T]]]]]] = newSeqWith(d1, newSeqWith(d2, newSeqWith(\n d3, newSeqWith(d4, newSeqWith(d5, newSeqWith(d6, default))))))\n discard\n"
ImportExpand "cplib/graph/graph.nim" <=== "when not declared CPLIB_GRAPH_GRAPH:\n const CPLIB_GRAPH_GRAPH* = 1\n\n type Graph*[T] = ref object of RootObj\n edges*: seq[seq[(int, T)]]\n\n type WeightedDirectedGraph*[T] = ref object of Graph[T]\n type WeightedUnDirectedGraph*[T] = ref object of Graph[T]\n type UnWeightedDirectedGraph* = ref object of Graph[int]\n type UnWeightedUnDirectedGraph* = ref object of Graph[int]\n\n type GraphTypes* = Graph or WeightedDirectedGraph or WeightedUnDirectedGraph or UnWeightedDirectedGraph or UnWeightedUnDirectedGraph\n\n proc add_edge_impl[T](g: GraphTypes, u, v: int, cost: T, directed: bool) =\n g.edges[u].add((v, cost))\n if not directed: g.edges[v].add((u, cost))\n\n #WeightedDirectedGraph\n proc initWeightedDirectedGraph*(N: int, edgetype: typedesc = int): WeightedDirectedGraph[edgetype] =\n result = WeightedDirectedGraph[edgetype](edges: newSeq[seq[(int, edgetype)]](N))\n proc add_edge*[T](g: var WeightedDirectedGraph[T], u, v: int, cost: T) =\n g.add_edge_impl(u, v, cost, true)\n\n #WeightedUnDirectedGraph\n proc initWeightedUnDirectedGraph*(N: int, edgetype: typedesc = int): WeightedUnDirectedGraph[edgetype] =\n result = WeightedUnDirectedGraph[edgetype](edges: newSeq[seq[(int, edgetype)]](N))\n proc add_edge*[T](g: var WeightedUnDirectedGraph[T], u, v: int, cost: T) =\n g.add_edge_impl(u, v, cost, false)\n\n #UnWeightedDirectedGraph\n proc initUnWeightedDirectedGraph*(N: int): UnWeightedDirectedGraph =\n result = UnWeightedDirectedGraph(edges: newSeq[seq[(int, int)]](N))\n proc add_edge*(g: var UnWeightedDirectedGraph, u, v: int) =\n g.add_edge_impl(u, v, 1, true)\n\n #UnWeightedUnDirectedGraph\n proc initUnWeightedUnDirectedGraph*(N: int): UnWeightedUnDirectedGraph =\n result = UnWeightedUnDirectedGraph(edges: newSeq[seq[(int, int)]](N))\n proc add_edge*(g: var UnWeightedUnDirectedGraph, u, v: int) =\n g.add_edge_impl(u, v, 1, false)\n discard\n"
ImportExpand "cplib/graph/dijkstra.nim" <=== "when not declared CPLIB_GRAPH_DIJKSTRA:\n #[ import cplib/graph/graph ]#\n import std/heapqueue\n import algorithm\n const CPLIB_GRAPH_DIJKSTRA* = 1\n proc restore_dijkstra*[T](G: Graph[T], start: int, ZERO: T = 0, INF: T = int(3300300300300300491)): tuple[costs: seq[T], prev: seq[int]] =\n var\n queue = initHeapQueue[(T, int)]()\n costs = newSeq[T](len(G.edges))\n prev = newseq[int](len(G.edges))\n costs.fill(INF)\n prev.fill(-1)\n queue.push((ZERO, start))\n costs[start] = ZERO\n while len(queue) != 0:\n var (cost, i) = queue.pop()\n if cost > costs[i]:\n continue\n for (j, c) in G.edges[i]:\n var temp = costs[i] + c\n if temp < costs[j]:\n prev[j] = i\n costs[j] = temp\n queue.push((temp, j))\n return (costs, prev)\n proc dijkstra*[T](G: Graph[T], start: int, ZERO: T = 0, INF: T = int(3300300300300300491)): seq[T] =\n var costs, _ = restore_dijkstra(G, start, ZERO, INF)\n return costs\n proc restore_shortestpath_from_prev*(prev: seq[int], goal: int): seq[int] =\n var i = goal\n while i != -1:\n result.add(i)\n i = prev[i]\n result = result.reversed()\n proc shortest_path*[T](G: Graph[T], start: int, goal: int, ZERO: T = 0, INF: T = int(3300300300300300491)): tuple[path: seq[int], cost: int] =\n var (costs, prev) = restore_dijkstra(G, start, ZERO, INF)\n result.path = prev.restore_shortestpath_from_prev(goal)\n result.cost = costs[goal]\n discard\n"
# see https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/mincostflow.nim
ImportExpand "atcoder/mincostflow.nim" <=== "when not declared ATCODER_MINCOSTFLOW_HPP:\n const ATCODER_MINCOSTFLOW_HPP* = 1\n\n import std/heapqueue\n import std/algorithm\n #[ import atcoder/internal_csr ]#\n when not declared ATCODER_INTERNAL_CSR_HPP:\n const ATCODER_INTERNAL_CSR_HPP* = 1\n \n type csr*[E] = object\n start*: seq[int]\n elist*: seq[E]\n proc initCsr*[E](n:int, edges:seq[(int, E)]):csr[E] =\n var start = newSeq[int](n + 1)\n var elist = newSeq[E](edges.len)\n for e in edges: start[e[0] + 1].inc\n for i in 1..n: start[i] += start[i - 1]\n var counter = start\n for e in edges:\n elist[counter[e[0]]] = e[1]\n counter[e[0]].inc\n return csr[E](start:start, elist:elist)\n discard\n #[ import atcoder/internal_queue ]#\n when not declared ATCODER_INTERNAL_QUEUE_HPP:\n const ATCODER_INTERNAL_QUEUE_HPP* = 1\n \n type simple_queue[T] = object\n payload:seq[T]\n pos:int\n proc init_simple_queue*[T]():auto = simple_queue[T](payload:newSeq[T](), pos:0)\n # TODO\n # void reserve(int n) { payload.reserve(n); }\n proc len*[T](self:simple_queue[T]):int = self.payload.len - self.pos\n proc empty*[T](self:simple_queue[T]):bool = self.pos == self.payload.len\n proc push*[T](self:var simple_queue[T], t:T) = self.payload.add(t)\n proc front*[T](self:simple_queue[T]):T = self.payload[self.pos]\n proc clear*[T](self:var simple_queue[T]) =\n self.payload.setLen(0)\n self.pos = 0;\n proc pop*[T](self:var simple_queue[T]) = self.pos.inc\n discard\n #[ import atcoder/internal_heap ]#\n when not declared ATCODER_INTERNAL_HEAP:\n const ATCODER_INTERNAL_HEAP* = 1\n proc push_heap*[T](v: var openArray[T], p:Slice[int]) {.inline.} =\n var i = p.b\n while i > 0:\n var p = (i - 1) shr 1\n if v[p] < v[i]: swap v[p], v[i]\n else: break\n i = p\n proc pop_heap*[T](v: var openArray[T], p:Slice[int]) {.inline.} =\n swap v[0], v[p.b]\n var p = p\n p.b.dec\n var i = 0\n while true:\n var (c0, c1) = (i * 2 + 1, i * 2 + 2)\n if c1 in p:\n if v[c1] > v[i]:\n if v[c0] > v[c1]:\n swap(v[i], v[c0])\n i = c0\n else:\n swap(v[i], v[c1])\n i = c1\n elif v[c0] > v[i]:\n swap(v[i], v[c0])\n i = c0\n else: break\n elif c0 in p:\n if v[c0] > v[i]:\n swap(v[i], v[c0])\n i = c0\n else: break\n else: break\n discard\n\n type MCFEdge*[Cap, Cost] = object\n src*, dst*: int\n cap*, flow*: Cap\n cost*: Cost\n\n type MCFInternalEdge[Cap, Cost] = object\n dst, rev: int\n cap: Cap\n cost: Cost\n\n type MCFGraph*[Cap, Cost] = object\n n:int\n edges:seq[MCFEdge[Cap, Cost]]\n \n proc initMCFGraph*[Cap, Cost](n:int):MCFGraph[Cap, Cost] = result.n = n\n proc initMinCostFLow*[Cap, Cost](n:int):MCFGraph[Cap, Cost] = result.n = n\n\n proc add_edge*[Cap, Cost](self: var MCFGraph[Cap, Cost], src, dst:int, cap:Cap, cost:Cost):int {.discardable.} =\n assert src in 0..<self.n\n assert dst in 0..<self.n\n assert 0 <= cap\n assert 0 <= cost\n var m = self.edges.len\n self.edges.add(MCFEdge[Cap, Cost](src:src, dst:dst, cap:cap, flow:0, cost:cost))\n return m\n\n proc get_edge*[Cap, Cost](self:MCFGraph[Cap, Cost], i:int): MCFEdge[Cap, Cost] =\n let m = self.edges.len\n assert i in 0..<m\n return self.edges[i]\n\n proc edges*[Cap, Cost](self:var MCFGraph[Cap, Cost]):seq[MCFEdge[Cap, Cost]] = self.edges\n type MCFQ[Cost] = object\n key:Cost\n dst:int\n proc `<`*[Cost](l, r:MCFQ[Cost]):bool = l.key > r.key\n\n proc slope*[Cap, Cost](self: MCFGraph[Cap, Cost], g:var csr[MCFInternalEdge[Cap, Cost]], s, t:int, flow_limit:Cap):seq[tuple[cap:Cap, cost:Cost]] =\n ## variants (C = maxcost):\n ## -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0\n ## reduced cost (= e.cost + dual[e.src] - dual[e.to]) >= 0 for all edge\n\n ## dual_dist[i] = (dual[i], dist[i])\n var\n dual_dist = newSeq[tuple[dual, dist:Cost]](self.n)\n prev_e = newSeq[int](self.n)\n vis = newSeq[bool](self.n)\n que_min = newSeq[int]()\n que = newSeq[MCFQ[Cost]]()\n proc dual_ref(g:csr[MCFInternalEdge[Cap, Cost]]):bool =\n for i in 0..<self.n: dual_dist[i].dist = Cost.high\n vis.fill(false)\n que_min.setLen(0)\n que.setLen(0)\n\n # que[0..heap_r) was heapified\n var heap_r = 0\n\n dual_dist[s].dist = 0\n que_min.add(s)\n while que_min.len > 0 or que.len > 0:\n var v:int\n if que_min.len > 0:\n v = que_min.pop()\n else:\n while heap_r < que.len:\n heap_r.inc\n que.push_heap(0 ..< heap_r)\n v = que[0].dst\n que.pop_heap(0 ..< que.len)\n discard que.pop()\n heap_r.dec\n if vis[v]: continue\n vis[v] = true\n if v == t: break\n ## dist[v] = shortest(s, v) + dual[s] - dual[v]\n ## dist[v] >= 0 (all reduced cost are positive)\n ## dist[v] <= (n-1)C\n let (dual_v, dist_v) = dual_dist[v]\n for i in g.start[v] ..< g.start[v + 1]:\n let e = g.elist[i]\n if e.cap == Cap(0): continue\n ## |-dual[e.to] + dual[v]| <= (n-1)C\n ## cost <= C - -(n-1)C + 0 = nC\n let cost = e.cost - dual_dist[e.dst].dual + dual_v\n if dual_dist[e.dst].dist - dist_v > cost:\n let dist_to = dist_v + cost\n dual_dist[e.dst].dist = dist_to\n prev_e[e.dst] = e.rev\n if dist_to == dist_v:\n que_min.add(e.dst)\n else:\n que.add(MCFQ[Cost](key:dist_to, dst:e.dst))\n if not vis[t]:\n return false\n\n for v in 0..<self.n:\n if not vis[v]: continue\n # dual[v] = dual[v] - dist[t] + dist[v]\n # = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +\n # (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,\n # t) + dual[t] + shortest(s, v) = shortest(s, v) -\n # shortest(s, t) >= 0 - (n-1)C\n dual_dist[v].dual -= dual_dist[t].dist - dual_dist[v].dist\n return true\n var\n flow:Cap = 0\n cost:Cost = 0\n prev_cost_per_flow:Cost = -1\n result = @[(Cap(0), Cost(0))]\n while flow < flow_limit:\n if not g.dual_ref(): break\n var c = flow_limit - flow\n block:\n var v = t\n while v != s:\n c = min(c, g.elist[g.elist[prev_e[v]].rev].cap)\n v = g.elist[prev_e[v]].dst\n block:\n var v = t\n while v != s:\n var e = g.elist[prev_e[v]].addr\n e[].cap += c\n g.elist[e[].rev].cap -= c\n v = g.elist[prev_e[v]].dst\n let d = -dual_dist[s].dual\n flow += c\n cost += c * d\n if prev_cost_per_flow == d:\n discard result.pop()\n result.add((flow, cost))\n prev_cost_per_flow = d\n\n proc slope*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int, flow_limit:Cap):seq[tuple[cap:Cap, cost:Cost]] =\n assert s in 0..<self.n\n assert t in 0..<self.n\n assert s != t\n\n let m = self.edges.len\n var edge_idx = newSeq[int](m)\n\n var g = block:\n var degree = newSeq[int](self.n)\n var redge_idx = newSeq[int](m)\n var elist = newSeqOfCap[(int, MCFInternalEdge[Cap, Cost])](2 * m)\n for i in 0..<m:\n let e = self.edges[i]\n edge_idx[i] = degree[e.src]\n degree[e.src].inc\n redge_idx[i] = degree[e.dst]\n degree[e.dst].inc\n elist.add((e.src, MCFInternalEdge[Cap, Cost](dst: e.dst, rev: -1, cap:e.cap - e.flow, cost:e.cost)))\n elist.add((e.dst, MCFInternalEdge[Cap, Cost](dst: e.src, rev: -1, cap:e.flow, cost: -e.cost)))\n var g = initCSR[MCFInternalEdge[Cap, Cost]](self.n, elist)\n for i in 0..<m:\n let e = self.edges[i]\n edge_idx[i] += g.start[e.src]\n redge_idx[i] += g.start[e.dst]\n g.elist[edge_idx[i]].rev = redge_idx[i];\n g.elist[redge_idx[i]].rev = edge_idx[i];\n g\n\n result = self.slope(g, s, t, flow_limit)\n\n for i in 0..<m:\n let e = g.elist[edge_idx[i]]\n self.edges[i].flow = self.edges[i].cap - e.cap\n proc flow*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int, flow_limit:Cap):tuple[cap:Cap, cost:Cost] = self.slope(s, t, flow_limit)[^1]\n proc flow*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int):tuple[cap:Cap, cost:Cost] = self.flow(s, t, Cap.high)\n proc slope*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int):seq[tuple[cap:Cap, cost:Cost]] = self.slope(s, t, Cap.high)\n\n #### chaemon added\n proc reset*[Cap, Cost](self: var MCFGraph[Cap, Cost]) =\n for e in self.edges.mitems:\n e.flow = 0\n\n proc set_edge*[Cap, Cost](self: var MCFGraph[Cap, Cost], i:int, cap:Cap, cost:Cost) =\n assert 0 <= cap\n assert 0 <= cost\n var m = self.edges.len\n assert i in 0 ..< m\n edges[i].cap = cap\n edges[i].cost = cost\n discard\n"
var k,n,m = input(int)
var a = input(int, k)
var b = input(int, n)
var g = initMCFGraph[int,int](n+k+2)
var gd = initWeightedUnDirectedGraph(n, int)
for i in 0..<m:
var u,v = input(int)-1
var d = input(int)
gd.add_edge(u,v,d)
var d = newSeq[seq[int]](0)
for i in 0..<n:
var (costs, prv) = gd.restore_dijkstra(i)
d.add(costs)
# debug(costs)
# var mx = d.mapIt(it.max).max
var s = n+k
var t = s+1
for i in 0..<k: g.add_edge(s, i, 1, 0)
for i in 0..<n: g.add_edge(i+k, t, b[i], 0)
for i in 0..<k:
for j in 0..<n:
g.add_edge(i, j+k, 1, d[a[i]-1][j])
var (f, c) = g.flow(s, t)
# for e in g.edges: echo e
# debug(f)
print(c)