結果
問題 | No.1565 Union |
ユーザー | 👑 tatt61880 |
提出日時 | 2021-06-27 04:56:09 |
言語 | Kuin (KuinC++ v.2021.9.17) |
結果 |
AC
|
実行時間 | 683 ms / 2,000 ms |
コード長 | 2,362 bytes |
コンパイル時間 | 3,147 ms |
コンパイル使用メモリ | 150,644 KB |
実行使用メモリ | 65,280 KB |
最終ジャッジ日時 | 2024-04-29 02:54:08 |
合計ジャッジ時間 | 13,649 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 227 ms
30,848 KB |
testcase_11 | AC | 359 ms
44,544 KB |
testcase_12 | AC | 428 ms
46,336 KB |
testcase_13 | AC | 120 ms
17,536 KB |
testcase_14 | AC | 484 ms
51,712 KB |
testcase_15 | AC | 679 ms
65,280 KB |
testcase_16 | AC | 510 ms
64,640 KB |
testcase_17 | AC | 669 ms
65,224 KB |
testcase_18 | AC | 683 ms
65,280 KB |
testcase_19 | AC | 655 ms
65,244 KB |
testcase_20 | AC | 317 ms
64,640 KB |
testcase_21 | AC | 320 ms
64,640 KB |
testcase_22 | AC | 323 ms
64,640 KB |
testcase_23 | AC | 320 ms
64,640 KB |
testcase_24 | AC | 319 ms
64,640 KB |
testcase_25 | AC | 350 ms
64,640 KB |
testcase_26 | AC | 335 ms
64,640 KB |
testcase_27 | AC | 343 ms
64,768 KB |
testcase_28 | AC | 346 ms
64,640 KB |
testcase_29 | AC | 337 ms
64,640 KB |
ソースコード
func main() var n: int :: cui@inputInt() var m: int :: cui@inputInt() var graph: []list<Edge> :: #[n]list<Edge> for i(0, n - 1) do graph[i] :: #list<Edge> end for for i(0, m - 1) var a: int :: cui@inputInt() - 1 var b: int :: cui@inputInt() - 1 var c: int :: 1 do graph[a].add((#Edge).init(b, c)) do graph[b].add((#Edge).init(a, c)) end for var res: []int :: dists(graph, 0) var ans: int :: res[n - 1] if(ans = lib@intMax) do ans :: -1 end if do cui@print("\{ans}\n") func dists(graph: []list<Edge>, start: int): []int var res: []int :: [lib@intMax].repeat(^graph) do res[start] :: 0 var pq: PriorityQueue :: #PriorityQueue do pq.add(-(0 + start)) while loop(pq.len <> 0) var data: int :: -pq.top() do pq.pop() var u: int :: data % 10 ^ 6 if(res[u] < data / 10 ^ 6) skip loop end if do graph[u].head() for i(0, ^graph[u] - 1) var e: Edge :: graph[u].get() var v: int :: e.v var dist: int :: e.dist if(res[u] + dist < res[v]) do res[v] :: res[u] + dist do pq.add(-(res[v] * 10 ^ 6 + v)) end if do graph[u].next() end for end while ret res class PriorityQueue() var data: []int +var len: int *func ctor() do me.data :: #[1024]int do me.len :: 0 end func +func add(elem: int) var n: int :: me.len if(^me.data = me.len) do me.data :~ #[me.len]int end if do me.data[me.len] :: elem do me.len :+ 1 while(n <> 0) var i: int :: (n - 1) / 2 if(me.data[n] > me.data[i]) var tmp: int :: me.data[n] do me.data[n] :: me.data[i] do me.data[i] :: tmp end if do n :: i end while end func +func pop() var n: int :: me.len - 1 do me.data[0] :: me.data[n] do me.len :- 1 var i: int :: 0 var j: int :: 1 while(j < n) if(j <> n - 1 & me.data[j] < me.data[j + 1]) do j :+ 1 end if if(me.data[i] < me.data[j]) var tmp: int :: me.data[j] do me.data[j] :: me.data[i] do me.data[i] :: tmp end if do i :: j do j :: 2 * i + 1 end while end func +func top(): int ret me.data[0] end func end class end func class Edge() +var v: int +var dist: int +func init(v: int, dist: int): Edge do me.v :: v do me.dist :: dist ret me end func end class end func