「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題！

問題概要

頂点数 $N$ 、辺数 $M$ の重み付き無向グラフが与えられる。頂点番号は $1, 2, \dots, N$ とする。 $i$ 番目の辺は頂点 $a_{i}, b_{i}$ を結んでおり、その重みは $c_{i}$ である。

このグラフの頂点のうち $L$ 個の特別な頂点 $J_{1}, J_{2}, \dots, J_{L}$ があって、その頂点には SIRO というラーメン店がある。これらの頂点に立ち寄ったとき、ラーメンを食べるのに要する時間は $E_{1}, E_{2}, \dots, E_{L}$ である。

さて、あなたは今、頂点 $S$ にいる。いまからあなたは $T$ 秒以内にグラフを移動して、できるだけ多くの SIRO のある頂点でラーメンを食べて、最終的に頂点 $S$ に帰って来たい。

食べることのできるラーメン数の最大値を求めよ。

制約

$2 \le N \le 200$
$1 \le M \le 5000$
$1 \le L \le 16$

考えたこと

すべて 0-indexed で考える。SIRO というラーメン店のある頂点を SIRO 頂点と呼ぶことにする。

元のグラフに対して、SIRO 頂点と、スタート頂点からなる、頂点数 $L+1$ のグラフを作る。

頂点 $0, 1, \dots, L-1$ は、元のグラフの頂点 $J_{0}, J_{1}, \dots, J_{L-1}$ に対応する
頂点 $L$ は、元のグラフの頂点 $S$ に対応する
辺 $(i, j)$ の重みは、元のグラフ上で対応する頂点間の最短距離とする

こうしたグラフは、 $L+1$ 個の頂点を始点とした Dijkstra 法によって、 $O(LN\log M)$ の計算量で構築できる。

元の問題は、このグラフ上で TSP に近いことをする問題となる。このグラフは頂点数が $L+1 \le 19$ であり、とても頂点数が小さいという特徴をもつ。よって、次の配列 dp を求める bit DP で間に合う。

dp[S][v] ← すでにラーメンを食べた頂点 (頂点 $S$ を除く) の集合が $S$ であり、最後に訪れた頂点が $v$ である場合について、その状態を達成するまでの最短時間

計算量は $O(LN \log M + 2^{L}L^{2})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Edge = pair<int, long long>;
using Graph = vector<vector<Edge>>;
const long long INF = 1LL<<60;

// 頂点 s を始点としたグラフ探索
vector<long long> Dijkstra(const Graph &G, int s) {
    vector<long long> dist(G.size(), INF);
    dist[s] = 0;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> que;
    que.push({0, s});
    while (!que.empty()) {
        auto [cur, v] = que.top();
        que.pop();
        if (dist[v] < cur) continue;
        for (const auto &e : G[v]) {
            if (chmin(dist[e.first], dist[v] + e.second)) {
                que.push({dist[e.first], e.first});
            }
        }
    }
    return dist;
}

int solve(int N, int M, int L, int S, int T) {
    --S;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        long long a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    
    // SIRO info
    vector<long long> J(L), E(L);
    for (int i = 0; i < L; ++i) {
        cin >> J[i] >> E[i];
        --J[i];
    }
    J.push_back(S), E.push_back(0);
    int s = L++;

    // make graph
    vector<vector<long long>> G2(L, vector<long long>(L, INF));
    for (int i = 0; i < L; ++i) {
        const auto &dist = Dijkstra(G, J[i]);
        for (int j = 0; j < L; ++j) G2[i][j] = dist[J[j]];
    }
    
    // bit DP: dp[S][v] := 頂点集合 S をすべて通って、最後にいる頂点が v であるときの、最小コスト
    vector<vector<long long>> dp(1<<L, vector<long long>(L, INF));
    dp[1<<s][s] = 0;
    for (int bit = 0; bit < (1<<L); ++bit) {
        for (int v = 0; v < L; ++v) {
            for (int v2 = 0; v2 < L; ++v2) {
                int nbit = bit | (1<<v2);
                dp[nbit][v2] = min(dp[nbit][v2], dp[bit][v] + G2[v][v2] + E[v2]);
            }
        }
    }
    
    // dp[bit][g] <= T となる bit について、最多お菓子数を求める
    int res = -1;
    for (int bit = 0; bit < (1<<L); ++bit) {
        for (int v = 0; v < L; ++v) {
            if (dp[bit][v] + G2[v][s] <= T) chmax(res, __builtin_popcount(bit) - 1);
        }
    }
    return res;
}

int main() {
    int N, M, L, S, T;
    while (cin >> N >> M >> L >> S >> T, N) {
        cout << solve(N, M, L, S, T) << endl;
    }
}