結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー ID 21712
提出日時 2026-05-01 03:04:34
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 1,873 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,861 ms
コンパイル使用メモリ 287,636 KB
実行使用メモリ 37,248 KB
最終ジャッジ日時 2026-05-01 03:04:53
合計ジャッジ時間 17,811 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

func main() {
	rd:=bf.NewReader(Stdin)
	var n,m int
	Fscan(rd,&n,&m)
	graph := make([][]int, n)
	for i := 0; i < m; i++ {
		var u,v int
		Fscan(rd, &u, &v)
		u--
		v--
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}
	iwai := make([]bool, n)
	var k int
	Fscan(rd, &k)
	for i := 0; i < k; i++ {
		var a int
		Fscan(rd,&a)
		iwai[a-1] = true
	}
	
	ans := solve(n, graph, iwai)
	
	Println(ans)
}

func solve(n int, graph [][]int, iwai []bool) int {
	
	// 解説読んだ
	// 拡張BFSって何…
	// 難しいすぎ
	// 自前解法のACコードはコーナーケースありそうで怪しいので
	// 解説のとおりに実装して経験を積む
	
	// 頂点番号をid、連続遭遇回数をcountとすると
	// 新しい頂点番号を id*5+count で定義
	
	// 星人いない頂点同士のパスはcount==0の頂点同士で結ぶ
	// いる頂点からいない頂点はcount>0からcount==0への頂点へ結ぶ
	// いる頂点への移動はcount+1への頂点へ移動する
	
	// グラフの作りなおし
	
	newG := make([][]int, 5*n)
	for i, es := range graph {
		if iwai[i] {
			for c := 1; c <= 4; c++ {
				ii := i*5+c
				for _, e := range es {
					ee := e*5
					if iwai[e] {
						if c == 4 {
							continue
						}
						ee += c+1
					}
					newG[ii] = append(newG[ii], ee)
				}
			}
		} else {
			ii := i*5
			for _, e := range es {
				ee := e*5
				if iwai[e] {
					ee++
				}
				newG[ii] = append(newG[ii], ee)
			}
		}
	}
	
	dist := make([]int, 5*n)
	for i := range dist {
		dist[i] = -1
	}

	dist[0] = 0	
	cur := []int{ 0 } 
	
	for len(cur) > 0 {
		tmp := []int{}
		for _, p := range cur {
			for _, e := range newG[p] {
				if dist[e] < 0 {
					dist[e] = dist[p]+1
					tmp = append(tmp, e)
				}
			}
		}
		cur = tmp
	}
	
	return dist[(n-1)*5]
}
0