标签：0x3f int rep cin TravellingPurchasingMan dp dis

Topcoder #Floyd #状压dp

Floyd 跑全源最短路，然后 \(dp_{msk,x}\) 表示在 \(msk\) 购物过，并且最后一次在 \(x\) 的最小完成时间，枚举一个转移即可，时间复杂度是 \(\mathcal{O}(n^3+2^kk\)) 的

// Author: xiaruize
const int N = 55 + 10;

int n, m, t;
struct node
{
    int s, t, val;
} s[N];
vector<pii> g[N];
int dis[N][N];
int dp[100005][16];

void solve()
{
    mms(dp, 0x3f);
    mms(dis, 0x3f);
    cin >> n;
    cin >> t;
    rep(i, 0, t - 1)
    {
        cin >> s[i].s >> s[i].t >> s[i].val;
    }
    cin >> m;
    rep(i, 1, m)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }
    rep(i, 0, n - 1) dis[i][i] = 0;
    rep(k, 0, n - 1)
    {
        rep(i, 0, n - 1)
        {
            rep(j, 0, n - 1)
            {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    int res = 0;
    rep(i, 0, t - 1)
    {
        // if (dis[i][n - 1] != INF)
        debug(i, dis[i][n - 1]);
        if (dis[i][n - 1] <= s[i].t)
            dp[(1 << i)][i] = max(dis[i][n - 1], s[i].s) + s[i].val;
    }
    rep(msk, 1, (1 << t) - 1)
    {
        rep(v, 0, t - 1)
        {
            if (msk & (1 << v))
            {
                rep(u, 0, t - 1)
                {
                    if (u != v && (msk & (1 << u)))
                    {
                        int p = dp[msk ^ (1 << v)][u] + dis[u][v];
                        if (p <= s[v].t)
                        {
                            dp[msk][v] = min(dp[msk][v], max(p, s[v].s) + s[v].val);
                        }
                    }
                }
            }
            if (dp[msk][v] < 1e9)
            {
                debug(msk, v);
                res = max(res, __builtin_popcount(msk));
            }
        }
    }
    cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：0x3f,int,rep,cin,TravellingPurchasingMan,dp,dis
From： https://www.cnblogs.com/xiaruize/p/18136774