square869120-G Revenge of Traveling Salesman Problem

以下に書く、巡回セールスマン問題の亜種の実装。
algo-logic の bit DP のページに再帰の実装があるので、それのループ版をここに書き留める。

##問題概要
各辺に利用期限が課された重み付き無向グラフが与えられたとき、そのグラフ上の巡回セールスマン問題の最短経路長と最短経路数を求めよ。
https://atcoder.jp/contests/s8pc-1/tasks/s8pc_1_g

##実装

#define rp(i, n) for (int i = 0; i < n; ++i)
typedef long long ll;
typedef unsigned long long ull;

template <class S, class T>
inline bool chmin(S &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

struct edge {
    ull to;
    ull dist;
    ull time;
    edge() {}
    edge(const ull &to, const ull &d, const ull &time)
        : to(to), dist(d), time(time) {}
};

int main() {
    //--- input
    int n,m;
    cin >> n >> m;
    using graph = vector<vector<edge>>;
    graph g(n);
    rp(i, m) {
        ull u, v, d, t;
        cin >> u >> v >> d >> t;
        // 0-indexed
        --u, --v;
        g[u].emplace_back(v, d, t);
        g[v].emplace_back(u, d, t);
    }
    //--- init bit dp
    const ll setbit = 1 << n;
    // value of dp: {dist, #path}
    using pll = pair<ll, ll>;
    vector<vector<pll>> dp(setbit, vector<pll>(n, {INF, 0}));
    dp[0][0] = {0, 1};
    // --- run bitdp
    for (ll bit = 0; bit < setbit; ++bit) rp(v, n) for (auto e : g.at(v)) {
            // consider traveling v -> u
            // skip if current set does not contain v
            if (bit != 0 && !((1 << v) & bit)) continue;
            const auto cost = e.dist + dp[bit][v].first;
            const auto u    = e.to;
            // first visit of u in time ?
            if (!(bit & (1 << u)) && cost <= e.time) {
                auto &dest = dp[bit | (1 << u)][u];
                if (dest.first == cost) {
                    // add #(new route) to current #path if you find another equally best route
                    dest.second += dp[bit][v].second;
                } else {
                    // set #path = #(new route) if best route updated
                    if (chmin(dest.first, cost))
                        dest.second = dp[bit][v].second;
                }
            }
        }

    //--- show result
    const string fail = "IMPOSSIBLE";
    const auto &res   = dp[setbit - 1][0];
    if (res.second != 0)
        cout << res.first << " " << res.second << endl;
    else
        cout << fail << endl;
}