結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー ID 21712
提出日時 2026-05-01 02:09:31
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
WA  
実行時間 -
コード長 2,391 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,961 ms
コンパイル使用メモリ 287,152 KB
実行使用メモリ 19,456 KB
最終ジャッジ日時 2026-05-01 02:09:48
合計ジャッジ時間 15,544 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

const DEBUG = false

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 {
	
	dist := make([]int, n)
	for i := range dist {
		dist[i] = -1
	}
	
	dist[0] = 0
	
	count := make([]int, n)
	
	times := make([]int, n)
	backs := make([]int, n)
	
	points := make([][]int, 10*n)
	retries := make([][]int, 10*n)
	flag := make([]bool, 10*n)
	rps := []int{}
	
	points[0] = []int{ 0 }
	
	t := 1

	for d := 0; len(points[d]) > 0; d++ {
		ps := points[d]
		points[d] = nil
		next := []int{}
		for _, p := range ps {
			for _, e := range graph[p] {
				if dist[e] < 0 {
					if iwai[e] {
						if count[p] == 4 {
							continue
						}
						count[e] = count[p]+1
					} else {
						count[e] = 0
					}
					dist[e] = d+1
					times[e] = t
					backs[e] = count[p]
					next = append(next, e)
				} else if dist[e] == d {
					if iwai[e] {
						count[e] = min(count[e], count[p]+1)
						times[e] = t
					}
					backs[e] = min(backs[e], count[p])
				} else if iwai[e] && times[e] < t {
					if count[p] == 4 {
						continue
					}
					dist[e] = d+1
					count[e] = count[p]+1
					times[e] = t
					backs[e] = count[p]
					next = append(next, e)
				}
			}
		}
		for _, p := range next {
			if !iwai[p] && backs[p] > 0 {
				retries[d+1] = append(retries[d+1], p)
			}
		}
		if len(retries[d+1]) > 0 {
			if !flag[d+1] {
				flag[d+1] = true
				rps = append(rps, d+1)
			}
		}
		points[d+1] = next

		if DEBUG {
			println("d=",d,",t=",t)
			println(Sprintf("ps=%#v",ps))
			println(Sprintf("next=%#v",next))
			println(Sprintf("retries[d+1]=%#v",retries[d+1]))
			println(Sprintf("dist =%#v",dist))
			println(Sprintf("count=%#v",count))
			println(Sprintf("times=%#v",times))
			println(Sprintf("backs=%#v",backs))
		}
		
		if len(next) == 0 && len(rps) > 0 {
			rn := len(rps)
			d = rps[rn-1]
			rps = rps[:rn-1]
			points[d] = retries[d]
			retries[d] = nil
			flag[d] = false
			d--
			t++
		}

	}
	
	return dist[n-1]
}
0