AtCoder Beginner Contest 301 E

https://atcoder.jp/contests/abc301/tasks/abc301_e

SとGとお菓子マスの距離のグラフにします。そして、グラフをたどっていって、今の位置と今までたどった位置を状態とみなし、その状態の最短距離を求めます。ただ、間に合わないので、各ステップで状態数を距離ソートして10万で打ち切るというインチキをしています。

// Pac-Takahashi
#![allow(non_snake_case)]

use std::collections::{VecDeque, HashMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

//////////////////// process ////////////////////

type Map = Vec<Vec<char>>;
type Node = (usize, usize);

fn read_input() -> (usize, Map) {
    let v = read_vec();
    let H = v[0];
    let T = v[2];
    let A = (0..H).map(|_| read::<String>().chars().collect::<Vec<char>>()).
                                                            collect::<Map>();
    (T, A)
}

fn collect_nodes(A: &Map) -> Vec<Node> {
    let mut nodes: Vec<(usize, usize)> = Vec::new();
    let H = A.len();
    let W = A[0].len();
    for i in 0..W {
        for j in 0..H {
            if A[j][i] == 'S' {
                nodes.push((i, j))
            }
        }
    }
    for i in 0..W {
        for j in 0..H {
            if A[j][i] == 'o' {
                nodes.push((i, j))
            }
        }
    }
    for i in 0..W {
        for j in 0..H {
            if A[j][i] == 'G' {
                nodes.push((i, j))
            }
        }
    }
    nodes
}

fn neighbors(node: &Node, A: &Map) -> Vec<Node> {
    let (x, y) = node;
    let H = A.len();
    let W = A[0].len();
    
    let is_inner = |(x, y): &Node| {
        0 < *x && *x <= W && 0 < *y && *y <= H && A[y-1][x-1] != '#'
    };
    
    // 負にならないように1個ずつずらす
    vec![(x+2, y+1), (x+1, y+2), (*x, y+1), (x+1, *y)].into_iter().
                filter(|v| is_inner(v)).
                map(|(x1, y1)| (x1-1, y1-1)).collect::<Vec<Node>>()
}

fn make_distances(node: &Node, nodes: &Vec<Node>, A: &Map) -> Vec<usize> {
    let mut dists: HashMap<Node, usize> = HashMap::new();
    let mut queue = VecDeque::new();
    queue.push_back(*node);
    dists.insert(*node, 0);
    while let Some(v) = queue.pop_front() {
        let neis = neighbors(&v, &A);
        let dist = dists.get(&v).unwrap().clone();
        for w in neis.into_iter() {
            if !dists.contains_key(&w) {
                dists.insert(w, dist + 1);
                queue.push_back(w)
            }
        }
    }
    nodes.iter().map(|v| match dists.get(v) { Some(d) => *d, None => INF }).
                                                        collect::<Vec<usize>>()
}

fn make_distance_table(nodes: &Vec<Node>, A: &Map) -> Vec<Vec<usize>> {
    nodes.iter().map(|v| make_distances(v, nodes, A)).
                                collect::<Vec<Vec<usize>>>()
}

const INF: usize = 10000000;

#[derive(Debug, Eq, PartialEq)]
struct Item {
    dist: usize,
    id: usize,
    flags: i32,
    value: i32
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.dist.cmp(&self.dist)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

type Dict = HashMap<(usize, i32), usize>;

fn step(dic: Dict, table: &Vec<Vec<usize>>, T: usize) -> Dict {
    let mut new_dic: Dict = HashMap::new();
    for ((i0, flags0), d0) in dic.into_iter() {
        for (i, d) in table[i0].iter().enumerate() {
            if i == i0 || ((flags0 >> i) & 1) == 1 {
                continue
            }
            let dist = d0 + d;
            let flags = flags0 | (1 << i);
            if dist <= T {
                let e = new_dic.entry((i, flags)).or_insert(dist);
                if *e > dist {
                    *e = dist
                }
            }
        }
    }
    new_dic
}

fn f(T: usize, A: Vec<Vec<char>>) -> i32 {
    let nodes = collect_nodes(&A);
    let table = make_distance_table(&nodes, &A);
    let N = table.len();
    let mut max_value: i32 = -1;
    let mut dic: Dict = HashMap::new();     // { (node, flags): dist }
    dic.insert((0, 1), 0);
    for s in 0..N-1 {
        dic = step(dic, &table, T);
        if dic.len() > 100000 {
            let mut a = dic.into_iter().collect::<Vec<((usize, i32), usize)>>();
            a.sort_by_key(|x| x.1);
            dic = a[..100000].into_iter().map(|x| *x).collect::<Dict>()
        }
        if dic.keys().any(|(i, _)| *i == N-1) {
            max_value = s as i32
        }
    }
    max_value
}

//////////////////// main ////////////////////

fn main() {
    let (T, A) = read_input();
    println!("{}", f(T, A))
}