AtCoder Beginner Contest 394 E

https://atcoder.jp/contests/abc394/tasks/abc394_e

始点と終点の両側から進めばいいと思います。入力例1の0⇒3なら、0の次は{a: [0], b: [1]}、3の前は{a:[2]}ですが、bは終点からはないのでaの([0], [2])のペアだけ残ります。こうやって進めていきます。ただ、どこまでたどればいいかは問題です。after contestがどうしても通りませんでした。

// Palindromic Shortest Path
#![allow(non_snake_case)]

use std::collections::{HashSet, 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()
}


//////////////////// DirectedGraph ////////////////////

type Node = usize;
type Weight = char;

struct DirectedGraph {
    g: Vec<Vec<(Node, Weight)>>
}

impl DirectedGraph {
    fn inverse(&self) -> DirectedGraph {
        let N = self.g.len();
        let mut g: Vec<Vec<(Node, Weight)>> = vec![vec![]; N];
        for i in 0..N {
            for &(j, w) in self.g[i].iter() {
                g[j].push((i, w))
            }
        }
        DirectedGraph { g }
    }
    
    fn has_path(&self, orig: Node, dest: Node) -> bool {
        let mut stack: Vec<Node> = vec![orig];
        let mut visited: HashSet<Node> = HashSet::new();
        visited.insert(orig);
        while let Some(v) = stack.pop() {
            for &(w, _) in self.g[v].iter() {
                if w == dest {
                    return true
                }
                else if !visited.contains(&w) {
                    stack.push(w);
                    visited.insert(w);
                }
            }
        }
        false
    }
    
    fn create(C: Vec<String>) -> DirectedGraph {
        let N = C.len();
        let mut g: Vec<Vec<(Node, Weight)>> = vec![vec![]; N];
        for i in 0..N {
            for (j, c) in C[i].chars().enumerate() {
                if c != '-' {
                    g[i].push((j, c))
                }
            }
        }
        DirectedGraph { g }
    }
}


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

fn read_input() -> Vec<String> {
    let N: usize = read();
    let C: Vec<String> = (0..N).map(|_| read()).collect();
    C
}

fn proceed_one_direction(s: &HashSet<Node>,
                            g: &DirectedGraph) -> HashMap<char, HashSet<Node>> {
    let mut dic: HashMap<char, HashSet<Node>> = HashMap::new();
    for &v in s.iter() {
        for &(w, c) in g.g[v].iter() {
            let e = dic.entry(c).or_insert(HashSet::new());
            (*e).insert(w);
        }
    }
    dic
}

fn proceed_each(s1: HashSet<Node>, s2: HashSet<Node>,
                graph1: &DirectedGraph, graph2: &DirectedGraph
                            ) -> (i32, Vec<(HashSet<Node>, HashSet<Node>)>) {
    // 前に進む
    let dic1 = proceed_one_direction(&s1, graph1);
    // s2と同じノードがあれば奇数の長さの回文
    for (_, &ref vs1) in dic1.iter() {
        for v1 in vs1.iter() {
            if s2.contains(&v1) {
                return (1, vec![])
            }
        }
    }
    
    let dic2 = proceed_one_direction(&s2, graph2);
    let mut vs: Vec<(HashSet<Node>, HashSet<Node>)> = vec![];
    for (c1, vs1) in dic1.into_iter() {
        if !dic2.contains_key(&c1) {
            continue
        }
        if let Some(vs2) = dic2.get(&c1) {
            if !vs1.is_disjoint(&vs2) {
                return (2, vec![])
            }
            vs.push((vs1, vs2.clone()))
        }
    }
    (0, vs)
}

fn proceed(v: Vec<(HashSet<Node>, HashSet<Node>)>, graph1: &DirectedGraph,
                                                   graph2: &DirectedGraph) ->
                                    (i32, Vec<(HashSet<Node>, HashSet<Node>)>) {
    let mut new_v: Vec<(HashSet<Node>, HashSet<Node>)> = vec![];
    let mut temp_ret: (i32, Vec<(HashSet<Node>, HashSet<Node>)>) = (0, vec![]);
    for (s1, s2) in v.into_iter() {
        let (code, vs) = proceed_each(s1, s2, graph1, graph2);
        if code == 1 {
            return (code, vs)
        }
        else if code == 2 {
            temp_ret = (code, vs)
        }
        else {
            new_v.extend(vs)
        }
    }
    
    if temp_ret.0 == 2 {
        temp_ret
    }
    else if new_v.is_empty() {
        (-1, new_v)
    }
    else {
        return (0, new_v)
    }
}

fn min_palindromic_path(i: Node, j: Node, graph1: &DirectedGraph,
                                          graph2: &DirectedGraph) -> i32 {
    if i == j {
        return 0
    }
    else if !graph1.has_path(i, j) {
        return -1
    }
    
    // 両側から調べる
    let mut v: Vec<(HashSet<Node>, HashSet<Node>)> = vec![];
    v.push((vec![i].into_iter().collect(), vec![j].into_iter().collect()));
    let N = graph1.g.len() as i32;
    for k in (0..N*5).step_by(2) {
        let (code, w) = proceed(v, graph1, graph2);
        if code == -1 {
            return -1
        }
        else if code != 0 {
            return k + code
        }
        v = w.clone()
    }
    -1
}

fn F(C: Vec<String>) {
    let N = C.len();
    let graph = DirectedGraph::create(C);
    let inv_graph = graph.inverse();
    for i in 0..N {
        let mut v: Vec<i32> = vec![0; N];
        for j in 0..N {
            v[j] = min_palindromic_path(i, j, &graph, &inv_graph)
        }
        println!("{}", v.into_iter().map(|d| d.to_string()).
                                            collect::<Vec<_>>().join(" "))
    }
}

fn main() {
    let C: Vec<String> = read_input();
    F(C)
}