Learning about bit DP

Before reading the article, you must know about bit operation.
If you don't know about it, I recommend to read this article

What is bit DP?

bit DP is a technique that can often be used in situations where you want to find the optimal permutation among possible permutations of n elements.
bit DP is a below dynamic programming framework.

• dp[S] := When optimizing the order within a subset S of the entire set{0, 1, ,..., n - 1), minimum cost in S.

In the bit DP framework, the following recurrence formula often holds:

• dp[S] = min(S, dp[S-i] + cost(S-i, i));

The following is a brief explanation of the meaning of this formula.
We want to compute the cost dp[S] of optimizing the order in it for S. We divide the case by what was the last element of the order.
If the last of S was i, then the optimal solution for the subset of S excluding the last i of S is dp[S- {i}]. If the increasing cost by adding i to S-{i} was cost(S-i, i), minimum cost is dp[S-i] + cost(S-i, i).

Then give i a try of all of them in the range of S and adopt the one that has the lowest cost.

Try to Solve a practical problem!

https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A

It is the problem of optimizing the order over n cities, so we can use bit DP.

However a little bit of ingenuity is required.
Looking at the bit DP's recurrence formula,

• dp[S] = min(S, dp[S-{i}] + cost(S-{i}, i)); S - i depends on which city was last, for example cost(u, i) if the last city was u, so we can't decide dp[S]. To solve it, we fix the dp table as below:
• dp[S][v] := the minimum cost in S for a subset S of the whole set {0, 1, ,..., n - 1} when the ordering is optimized with the constraint that the last is v.

DP reduction formulas can also be realized with a small modification:

• dp[S][v] = min(S, dp[S-v][u] + dist[u][v]);

Based on this, the implementation would be as follows

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

const INF: i64 = 1 << 60;

// main implementation
pub fn main() {
    input!(
        n: usize,
        m: usize,
        data: [(usize, usize, i64); m]
    );
    let dist = {
        let mut dist = vec![vec![INF; n]; n];
        for (s, t, d) in data {
            dist[s][t] = d;
        }
        dist
    };
    let mut dp = vec![vec![-1; n + 1]; 1 << n];
    let res = rec(n, 0, 0, &mut dp, &dist);
    if res != INF {
        println!("{}", res);
    } else {
        println!("-1");
    }
}

fn rec(n: usize, s: usize, now_v: usize, dp: &mut Vec<Vec<i64>>, dist: &Vec<Vec<i64>>) -> i64 {
    let mut res = INF;
    // Valid only if all have been explored and the current position is at the start.
    if s == (1 << n) - 1 {
        if now_v == 0 {
            dp[s][now_v] = 0;
        } else {
            dp[s][now_v] = INF;
        }
        return dp[s][now_v];
    }
    for v in 0..n {
        if (s >> v) & 1 == 0 && dist[v][now_v] != INF {
            res = res.min(rec(n, s | 1 << v, v, dp, dist) + dist[v][now_v]);
        }
    }
    dp[s][now_v] = res;
    dp[s][now_v]
}