結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー tokugh
提出日時 2025-11-01 16:20:03
言語 Julia
(2.11.2)
結果
AC  
実行時間 980 ms / 2,000 ms
コード長 2,554 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 7,972 KB
実行使用メモリ 297,460 KB
最終ジャッジ日時 2025-11-03 17:19:49
合計ジャッジ時間 55,141 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

toI(s=readline()) = parse(Int,s)
toVI(s=readline()) = map(toI,eachsplit(s))
rep(f,n) = [f() for _ in 1:n]
@enum YN Yes=1 No=0

function main()
    n,m = toVI()
    uv = rep(toVI,m)
    l = toI()
    jk = rep(toVI,l)
    res = solve(n,m,uv,l,jk)
    println(res == -1 ? "No" : "Yes\n$res")
end

function solve(n,m,uv,l,jk)
    to = [Int[] for _ in 1:n]
    for (u,v) in uv
        push!(to[u],v)
        push!(to[v],u)
    end
    h = IntHeap()
    r = fill(-1,n)
    for (j,k) in jk
        push!(h,(-k,j))
        r[j] = k
    end
    while !isempty(h)
        d,x = pop!(h)
        -d ≥ r[x] || continue
        for y in to[x]
            r[x]-1 > r[y] || continue
            if d != 0
                # @info "$((d+1,y)) pushed"
                r[y] = r[x]-1
                push!(h,(d+1,y))
            end
        end
    end
    r[1] == -1 || return -1
    dist = fill(-1,n)
    dist[1] = 0
    q = [1]
    while !isempty(q)
        x = popfirst!(q)
        for y in to[x]
            r[y] == -1 && dist[y] == -1 || continue
            dist[y] = dist[x] + 1
            push!(q,y)
        end
    end
    dist[n]
end

const T = Tuple{Int,Int}

struct IntHeap
    items :: Vector{T}
    function IntHeap()
        new(T[])
    end
    function IntHeap!(items::Vector{T})
        n = length(items)
        for i in 1:n heapify!_(items,i) end
        new(items)
    end
    IntHeap(src::AbstractVector{T}) = IntHeap!(Vector(src))
end

function heapify!_(items,i)
    # checkbounds(items,i)
    @inbounds while (j = i>>1) ≥ 1 && isless(items[i],items[j])
        items[j],items[i] = items[i],items[j]
        i = j
    end
end

function IntHeap(iter::Base.Generator)
    h = IntHeap()
    for x in iter push!(h,x) end
    return h
end

Base.length(h::IntHeap) = length(h.items)
Base.isempty(h::IntHeap) = isempty(h.items)

function Base.push!(h::IntHeap,x::T)
    (;items) = h
    push!(items,x)
    i = length(items)
    heapify!_(items,i)
    return h
end

function Base.pop!(h::IntHeap)
    n = length(h)
    n ≥ 1 || throw(ArgumentError("heap must be non-empty"))
    (;items) = h
    x,items[1] = items[1],items[n]
    pop!(items)
    isempty(items) && return x
    i = 1
    y = items[i]
    @inbounds while true
        j,j1 = 2i,2i+1
        if j1 < n
            z,z1 = items[j],items[j1]
            if isless(z1,z) j,z = j1,z1 end
        elseif j < n
            z = items[j]
        else
            break
        end
        isless(z,y) || break
        items[i] = z
        i = j
    end
    items[i] = y
    return x
end

main()
0