結果
問題 | No.1565 Union |
ユーザー | 小野寺健 |
提出日時 | 2021-12-19 10:25:36 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 442 ms / 2,000 ms |
コード長 | 2,202 bytes |
コンパイル時間 | 12,407 ms |
コンパイル使用メモリ | 224,456 KB |
実行使用メモリ | 27,376 KB |
最終ジャッジ日時 | 2023-12-20 13:08:42 |
合計ジャッジ時間 | 19,469 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 1 ms
6,676 KB |
testcase_06 | AC | 1 ms
6,676 KB |
testcase_07 | AC | 1 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 2 ms
6,676 KB |
testcase_10 | AC | 145 ms
7,908 KB |
testcase_11 | AC | 230 ms
16,404 KB |
testcase_12 | AC | 273 ms
12,368 KB |
testcase_13 | AC | 76 ms
7,776 KB |
testcase_14 | AC | 303 ms
16,596 KB |
testcase_15 | AC | 371 ms
23,176 KB |
testcase_16 | AC | 352 ms
23,124 KB |
testcase_17 | AC | 406 ms
25,256 KB |
testcase_18 | AC | 412 ms
25,260 KB |
testcase_19 | AC | 442 ms
25,244 KB |
testcase_20 | AC | 288 ms
27,356 KB |
testcase_21 | AC | 289 ms
27,360 KB |
testcase_22 | AC | 290 ms
27,364 KB |
testcase_23 | AC | 282 ms
27,356 KB |
testcase_24 | AC | 273 ms
25,296 KB |
testcase_25 | AC | 301 ms
25,224 KB |
testcase_26 | AC | 257 ms
25,192 KB |
testcase_27 | AC | 287 ms
25,228 KB |
testcase_28 | AC | 302 ms
27,376 KB |
testcase_29 | AC | 302 ms
27,360 KB |
ソースコード
package main import ( "fmt" "bufio" "os" "math" ) type Cell struct { item int next *Cell } func newCell(item int, cp *Cell) *Cell { newcp := new(Cell) newcp.item, newcp.next = item, cp return newcp } type Queue struct { size int front, rear *Cell } func newQueue() *Queue { newqp := new(Queue) newqp.size, newqp.front, newqp.rear = 0, nil, nil return newqp } func (q *Queue) enqueue(item int) { cp := newCell(item, nil) if q.size == 0 { q.front = cp q.rear = cp } else { q.rear.next = cp q.rear = cp } q.size++ } func (q *Queue) dequeue() (int, bool) { if q.size == 0 { return 0, false } else { item := q.front.item q.front = q.front.next q.size-- if q.size == 0 { q.rear = nil } return item, true } } func (q *Queue) isEmpty() bool { return q.size == 0 } type CellMgr struct { top, cp, last *Cell } func newCellMgr() *CellMgr { cmp := new(CellMgr) cmp.top = nil cmp.cp = nil cmp.last = nil return cmp } func (this *CellMgr) iterator() *CellMgr{ this.cp = this.top return this } func (this *CellMgr) append(item int) { ncp := newCell(item, nil) if this.top == nil { this.top = ncp this.last = ncp } else { this.last.next = ncp this.last = ncp } } func (this *CellMgr) isNext() bool { return this.cp != nil } func (this *CellMgr) next() (int, bool) { cp := this.cp if cp != nil { this.cp = cp.next return cp.item, true } else { return 0, false } } func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var N, M int fmt.Fscan(r, &N, &M) road := make([]*CellMgr, N) d := make([]int, N) for i := 0; i < N; i++ { road[i] = newCellMgr() d[i] = math.MaxInt64 } for i := 0; i < M; i++ { var a, b int fmt.Fscan(r, &a, &b) road[a-1].append(b-1) road[b-1].append(a-1) } d[0] = 0 q := newQueue() q.enqueue(0) var fin bool = false for !fin && !q.isEmpty() { v, _ := q.dequeue() rp := road[v].iterator() for rp.isNext() { nv , _ := rp.next() if d[nv] > d[v] + 1 { d[nv] = d[v] + 1 q.enqueue(nv) if nv == N-1 { fin = true break } } } } if fin { fmt.Fprintln(w, d[N-1]) } else { fmt.Fprintln(w, -1) } }