hdu 5418 Victor and World(floyd+상압 dp)

제목:

1부터 시작해서 모든 점을 거쳐 최종적으로 1로 돌아가는 데 필요한 최소값을 요구한다.

해결:

이것은 비교적 고전적인 여행사 문제로 이전에 비슷한 것을 한 적이 있다.먼저 플로이드로 모든 점 사이의 최단로를 구하세요.그리고 상태로 압축하여 16자리 한 명당 1은 이미 지나갔음을 표시하고 0은 지나지 않았다는 것을 표시하며 직접 위치로 연산하여 모든 상태를 표시한다.pp[st][j] 상태는 st이고 마지막으로 걷는 것은 j점의 최소값이다.이 경우 상태 이동 방정식은 dp[st|(1<(j - 1)][j]=min(dp[st|(1< (j - 1)][j], dp[st][i]+d[i][j]) 216∗n개 상태, n종이 이동하기 때문에 복잡도는 O(216?nn)
my code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f;
int d[N][N];
int dp[1<<N][N];
int n, m;

void floyd() {
    for(int i = 1; i <= n; i++) d[i][i] = 0;
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int tsp() {
    memset(dp,INF,sizeof(dp));
    dp[1][1] = 0;
    int end = (1<<n) - 1;
    for (int st=1; st <=end; st++)
        for(int i=1; i <= n; i++)
            for(int j=1; j <= n; j++) {
                if (i == j) continue;
                if ((1 << (i-1)) & st == 0 || (1 << (j-1) & st == 1)) continue;
                if (dp[st][i] == INF) continue;
                dp[st|(1<<(j-1))][j]=min(dp[st|(1<<(j-1))][j],dp[st][i]+d[i][j]);
            }
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans=min(ans, dp[end][i]+d[i][1]);
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(d, INF, sizeof(d));
        int u, v, val;
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &val);
            d[u][v] = min(d[u][v], val);
            d[v][u] = min(d[v][u], val);
        }
        floyd();
        printf("%d
", tsp());
    }
    return 0;
}