結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー ID 21712
提出日時 2026-05-24 15:23:06
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 269 ms / 2,000 ms
コード長 1,164 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,166 ms
コンパイル使用メモリ 283,652 KB
実行使用メモリ 25,276 KB
最終ジャッジ日時 2026-05-24 15:23:40
合計ジャッジ時間 22,628 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

func main() {
	rd := bf.NewReader(Stdin)
	var n,m int
	Fscan(rd,&n,&m)
	
	ds := make(map[int]int)
	
	graph := make([][]int,n)
	
	for i := 0; i < m; i++ {
		var s,t,d int
		Fscan(rd,&s,&t,&d)
		s--
		t--
		k := min(s,t)*n+max(s,t)
		if r, found := ds[k]; found {
			ds[k] = max(r, d)
		} else {
			ds[k] = d
			graph[s] = append(graph[s], t)
			graph[t] = append(graph[t], s)
		}
	}
	
	// BFS実装ミス…
	
	bfs := func(v int) int {
		visited := make([]bool, n)
		visited[0] = true
		cur := []int{0}
		cnt := 0
		for len(cur) > 0 {
			cnt++
			tmp := []int{}
			for _, p := range cur {
				for _, e := range graph[p] {
					if visited[e] {
						continue
					}
					k := min(p,e)*n+max(p,e)
					if ds[k] < v {
						continue
					}
					if e == n-1 {
						return cnt
					}
					visited[e] = true
					tmp = append(tmp, e)
				}
			}
			cur = tmp
		}
		return -1
	}
	
	overW := Search(1e9+1, func(v int) bool {
		return bfs(v) < 0
	})
	
	w := overW-1

	Println(w, bfs(w))
}

/*
考察

wを二分探索で決め打ちしてルートを幅優先探索する典型問題ぽい？

*/
0