题目 – luoguP1128

找出：从结点$1$出发，经过其他$n-1$个结点一次后，再回到结点$1$的最短路。

观察数据范围或者标签，考虑状压DP。用$n$位二进制数表示结点访问状态，$0$表示未访问，$1$表示已访问。设${f}_{i,\, j}$表示从结点$1$到结点$j$，状态为$i$的最短路。对于每一个01状态，用“1位”更新“0位”，即由已访问的结点更新未访问的结点。最后找最短路时还要加上回去的路。

int solve(){
    memset(f, 0x3f, sizeof f);
    f[1][1] = 0; // 一开始就是从1出发的
    for(int i = 0; i < (1 << n); i++){ // 每种01状态
        for(int j = 0; j < n; j++){
            if((i >> j) & 1) continue; // 先找0位
            for(int k = 0; k < n; k++){
                if((i >> k) & 1){ // 再找1位
                    int& t = f[i | (1 << j)][j + 1];
                    t = min(t, f[i][k + 1] + dis[k + 1][j + 1]);
                }
            }
        }
    }
    int res = 2e9;
    for(int i = 2; i <= n; i++){
        res = min(res, f[(1 << n) - 1][i] + dis[i][1]); // 要加上回去的dis[i][1]
    }
    return res;
}

后话

这道状压DP额外记录了一下，听说很经典。