一道可能不太明显的状压dp

为什么说不明显呢？因为可以状压的元素藏到了后面。

题意已经很清晰了：每个点一个颜色，找到一条最短的点数为\(k\)、恰好经过全部\(k\)种颜色的路径。你需要求出这条路径的长度。

虽然\(n \leq 100\)挺大的，但是\(k \leq 13\)，而我们要走的也只跟\(k\)有关，所以我们需要压缩\(k\)。

设dp[i][j]为当前走到下标为\(i\)的节点，走了颜色的状态为\(j\)的最短路径。

初始化挺简单的，就不讲了。

转移有点东西，看上去挺不可过的，但还是能过的。

首先枚举开辟颜色的当前状态，取出其中一个颜色，找到是这个颜色的节点，以她作为起点，再找当前没开辟过的颜色，找到所有是这个颜色的节点，对他们进行开辟。

可能不用判没路的情况，但我还是判了。

这样按照思路写一写，就可以过了！

所以数据可能有点水咯。。。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        const int maxn = 105;const int INF = 0x3f3f3f3f;int G[maxn][maxn];int dp[maxn][8200];// 目前走到i，取k个点的状态为j的最短路int w[maxn];int n, m, k;std::vector
        
          vec[14];// 我用vector存的int main(){    memset(G, 0x3f, sizeof G);    memset(dp, 0x3f, sizeof dp);    scanf("%d%d%d", &n, &m, &k);    for(int i = 1; i <= n; i++)    {        scanf("%d", &w[i]);         G[i][i] = 0;        vec[w[i]].push_back(i);    }    while(m--)    {        int u, v, w; scanf("%d%d%d", &u, &v, &w);        G[u][v] = std::min(G[u][v], w);    }    for(int i = 1; i <= n; i++)    {        dp[i][1 << w[i]] = 0;    }    int S = (1 << k) - 1;    for(int i = 1; i <= S; i++)// 状态    {        for(int j = 0; j < k; j++)        {            if((1 << j) & i)            {                int size1 = vec[j].size();                for(int l = 0; l < size1; l++)                {                    int u = vec[j][l];// 前节点                    for(int o = 0; o < k; o++)                    {                        if((1 << o) & i) continue;                        int size2 = vec[o].size();                        for(int p = 0; p < size2; p++)                        {                            int v = vec[o][p];                            if(G[u][v] != INF)                            {                                dp[v][i | (1 << o)] = std::min(dp[v][i | (1 << o)], dp[u][i] + G[u][v]);                            }                        }                    }                }            }        }    }    int ans = INF;    for(int i = 1; i <= n; i++) ans = std::min(ans, dp[i][S]);    if(ans == INF) printf("Ushio!\n");    else printf("%d\n", ans);    return 0;}