結果

問題 No.2565 はじめてのおつかい
ユーザー ID 21712
提出日時 2025-02-11 01:22:35
言語 Go
(1.23.4)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 1,115 bytes
コンパイル時間 16,994 ms
コンパイル使用メモリ 244,396 KB
実行使用メモリ 12,232 KB
最終ジャッジ日時 2025-02-11 01:23:03
合計ジャッジ時間 19,730 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "os"
import bf "bufio"

func main() {
	rd:=bf.NewReader(Stdin)
	var n, m int
	Fscan(rd, &n, &m)
	edges := make([][]int, n+1)
	for i := 0; i < m; i++ {
		var u, v int
		Fscan(rd, &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