結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー yiwiy9
提出日時 2026-09-04 23:04:08
言語 Rust
(1.97.1 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 51 ms / 2,000 ms
+ 565µs
コード長 1,851 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,336 ms
コンパイル使用メモリ 198,632 KB
実行使用メモリ 34,904 KB
最終ジャッジ日時 2026-09-04 23:07:58
合計ジャッジ時間 11,335 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        uv: [(Usize1, Usize1); m],
        l: usize,
        jk: [(Usize1, usize); l],
    }

    let mut graph_1 = vec![vec![]; n];
    for &(u, v) in &uv {
        graph_1[u].push(v);
        graph_1[v].push(u);
    }

    let watched = bfs_1(&graph_1, &jk);
    if watched[0] {
        println!("No");
        return;
    }

    let mut graph_2 = vec![vec![]; n];
    for &(u, v) in &uv {
        if !watched[u] && !watched[v] {
            graph_2[u].push(v);
            graph_2[v].push(u);
        }
    }

    let dist = bfs_2(&graph_2, 0);
    if dist[n - 1] == 1 << 30 {
        println!("No");
    } else {
        println!("Yes");
        println!("{}", dist[n - 1]);
    }
}

pub fn bfs_1(graph: &Vec<Vec<usize>>, jk: &[(usize, usize)]) -> Vec<bool> {
    let n = graph.len();
    let mut watched = vec![false; n];
    let mut que = std::collections::VecDeque::new();
    for &(j, k) in jk {
        watched[j] = true;
        que.push_back((j, k));
    }
    while let Some((u, k)) = que.pop_front() {
        if k == 0 {
            continue;
        }
        for &v in &graph[u] {
            if watched[v] {
                continue;
            }
            watched[v] = true;
            que.push_back((v, k - 1));
        }
    }
    watched
}

pub fn bfs_2(graph: &Vec<Vec<usize>>, s: usize) -> Vec<usize> {
    let inf = (1 << 30) as usize;
    let n = graph.len();
    let mut dist = vec![inf; n];
    let mut que = std::collections::VecDeque::new();
    dist[s] = 0;
    que.push_back(s);
    while let Some(u) = que.pop_front() {
        for &v in &graph[u] {
            if dist[v] != inf {
                continue;
            }
            dist[v] = dist[u] + 1;
            que.push_back(v);
        }
    }
    dist
}
0