HDU5418

12794 단어 HDUBestCoderTSP5418

HDU5418 Victor and World

  • 제의: 누드한 여행가 문제
  • 사고방식: 여행가 문제 누드 모델
  • 코드: 여기 3분 코드, 기억화 검색, dp, dp의 작은 최적화를 붙인다.
  • \\     
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int INF = 0x3f3f3f3f;
    const int maxn = 16;
    int Map[maxn][maxn];
    int dp[maxn][1<<maxn];
    int n, m;
    
    void floyd()
    {
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
                }
            }
        }
    }
    
    int solve(int S, int v)
    {
        if(dp[v][S] >= 0) {
            return dp[v][S];
        }
        if(S == (1<<n) - 1 && v == 0) {
            return 0;
        }
        int res = INF;
        for(int u = 0; u < n; u++) {
            if(Map[v][u] > 0 && !((S>>u)&1)) {
                res = min(res, Map[v][u] + solve(S|(1<<u), u));
            }
        }
        return dp[v][S] = res;
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while(T--) {
            for(int i = 0; i < maxn; i ++) {
                for(int j = 0; j < maxn; j++) {
                    Map[i][j] = INF;
                }
            }
            scanf("%d%d", &n, &m);
            for(int i = 0; i < m; i++) {
                int  u, v, w;
                scanf("%d%d%d", &u, &v, &w);
                u--; v--;
                Map[u][v] = min(Map[u][v], w);
                Map[v][u] = min(Map[v][u], w);
            }
            floyd();
            memset(dp, -1, sizeof(dp));
            if(n == 1) printf("0
    "
    ); else printf("%d
    "
    , solve(0, 0)); } return 0; }
    \\dp
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int INF = 0x3f3f3f3f;
    const int maxn = 16;
    int Map[maxn][maxn];
    int dp[maxn][1<<maxn];
    int n, m;
    
    void floyd()
    {
        for(int k = 0; k < n; k++)
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
    }
    
    int solve()
    {
        for(int i = 0; i < n; i++) {
            fill(dp[i], dp[i] + (1<<n), INF);
        }
    
        dp[0][(1<<n)-1] = 0;
        for(int S = (1<<n) - 2; S >= 0; S--) {
            for(int v = 0; v < n; v++) {
                for(int u = 0; u < n; u++) {
                    if(!((S>>u)&1)) {
                        dp[v][S] = min(dp[v][S], dp[u][S|1<<u] + Map[v][u]);
                    }
                }
            }
        }
        return dp[0][0];
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while(T--) {
            for(int i = 0; i < maxn; i ++) {
                fill(Map[i], Map[i] + maxn, INF);
            }
            scanf("%d%d", &n, &m);
            for(int i = 0; i < m; i++) {
                int  u, v, w;
                scanf("%d%d%d", &u, &v, &w);
                u--; v--;
                Map[u][v] = min(Map[u][v], w);
                Map[v][u] = min(Map[v][u], w);
            }
            floyd();
            if(n == 1) printf("0
    "
    ); else printf("%d
    "
    , solve()); } return 0; }
    \\dp   
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int INF = 0x3f3f3f3f;
    const int maxn = 16;
    int Map[maxn][maxn];
    int dp[maxn][1<<maxn];
    int n, m;
    
    void floyd()
    {
        for(int k = 0; k < n; k++)
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
    }
    
    int solve()
    {
        for(int i = 0; i < n; i++) {
            fill(dp[i], dp[i] + (1<<n), INF);
        }
    
        dp[0][(1<<n)-1] = 0;
        for(int S = (1<<n) - 2; S >= 0; S--) {
            for(int v = 0; v < n; v++) {
                if(S == 0 || (S>>v)&1) for(int u = 0; u < n; u++) {
                    if(!((S>>u)&1)) {
                        dp[v][S] = min(dp[v][S], dp[u][S|1<<u] + Map[v][u]);
                    }
                }
            }
        }
        return dp[0][0];
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while(T--) {
            for(int i = 0; i < maxn; i ++) {
                fill(Map[i], Map[i] + maxn, INF);
            }
            scanf("%d%d", &n, &m);
            for(int i = 0; i < m; i++) {
                int  u, v, w;
                scanf("%d%d%d", &u, &v, &w);
                u--; v--;
                Map[u][v] = min(Map[u][v], w);
                Map[v][u] = min(Map[v][u], w);
            }
            floyd();
            if(n == 1) printf("0
    "
    ); else printf("%d
    "
    , solve()); } return 0; }

    좋은 웹페이지 즐겨찾기