結果

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

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import "container/heap"

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)
	pq := new(PQ)
	
	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 || d+1 < dist[e] { 
					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
				heap.Push(pq, 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 && pq.Len() > 0 {
			d = heap.Pop(pq).(int)
			points[d] = retries[d]
			retries[d] = nil
			flag[d] = false
			d--
			t++
		}

	}
	
	return dist[n-1]
}

type PQ []int

func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Swap(i, j int) { pq[i],pq[j]=pq[j],pq[i] }
func (pq PQ) Less(i, j int) bool { return pq[i]<pq[j] }
func (pq *PQ) Push(v any) {
	*pq = append(*pq, v.(int))
}
func (pq *PQ) Pop() any {
	old := *pq
	n := len(old)
	v := old[n-1]
	*pq = old[:n-1]
	return v
}
0