結果

問題 No.2565 はじめてのおつかい
ユーザー ID 21712
提出日時 2025-02-11 01:16:29
言語 Go
(1.23.4)
結果
AC  
実行時間 1,322 ms / 2,000 ms
コード長 1,048 bytes
コンパイル時間 15,818 ms
コンパイル使用メモリ 236,176 KB
実行使用メモリ 10,492 KB
最終ジャッジ日時 2025-02-11 01:17:28
合計ジャッジ時間 55,137 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var n, m int
	Scan(&n, &m)
	edges := make([][]int, n+1)
	for i := 0; i < m; i++ {
		var u, v int
		Scan(&u, &v)
		edges[u] = append(edges[u], v)
	}
	var ans = -1
	if d, found := find(n, edges, 1, n-1, n, 1); found {
		ans = d
	}
	if d, found := find(n, edges, 1, n, n-1, 1); found {
		if d < ans || ans < 0 {
			ans = d
		}
	}
	Println(ans)
}

func find(n int, edges [][]int, points ...int) (distance int, found bool) {
	for i, p := range points[1:] {
		d, f := dist(n, edges, points[i], p)
		if !f {
			return
		}
		distance += d
	}
	found = true
	return
}

func dist(n int, edges [][]int, from, to int) (distance int, found bool) {
	visited := make([]bool, n+1)
	points := []int{from}
	visited[from] = true
	for len(points) > 0 {
		distance++
		next := []int{}
		for _, p := range points {
			for _, e := range edges[p] {
				if visited[e] {
					continue
				}
				if e == to {
					found = true
					return
				}
				visited[e] = true
				next = append(next, e)
			}
		}
		points = next
	}
	return
}
0