結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー ID 21712
提出日時 2026-05-24 14:53:44
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
WA  
実行時間 -
コード長 1,125 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,423 ms
コンパイル使用メモリ 287,900 KB
実行使用メモリ 23,048 KB
最終ジャッジ日時 2026-05-24 14:54:16
合計ジャッジ時間 20,006 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 38
権限があれば一括ダウンロードができます

ソースコード

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 := func(v int) int {
		visited := make([]bool, n)
		visited[0] = true
		cur := []int{0}
		cnt := 0
		for len(cur) > 0 {
			cnt++
			tmp := []int{}
			p := cur[0]
			cur = cur[1:]
			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