範例程式碼 uva10296

//uva10296
#include <iostream>
#include <algorithm>
#define MAXPOINT 1 + 15
#define INF 1000000000

using namespace std;

int matrix[MAXPOINT][MAXPOINT], odd[MAXPOINT], dp[1 << MAXPOINT];

// ref: http://mypaper.pchome.com.tw/zerojudge/post/1322922929
int build(int pN, int oddNum) {
    if(pN == 0)
        return 0;

    if(dp[pN] != -1)
        return dp[pN];

    int i, j, tmp;

    dp[pN] = 0xfffffff;
    for(int i = 0; i < oddNum; i++) {
        if(pN & (1 << i)) {
            for(j = i + 1; j < oddNum; j++) {
                if(pN & (1 << j)) {
                    tmp = build(pN - (1 << i) - (1 << j), oddNum);
                    dp[pN] = min(dp[pN], tmp + matrix[odd[i]][odd[j]]);
                }
            }
            break;
        }
    }
    return dp[pN];
}

int main()
{
    int pointNum, roadNum, pointInfo[MAXPOINT], total, x, y, len, oddNum;

    while(cin >> pointNum)  // get point number
    {
        if(pointNum == 0)
            break;

        // get road number
        cin >> roadNum;

        // initialize
        total = 0;
        for(int p = 0; p <= pointNum; p++)
            pointInfo[p] = 0;

        for(int i = 0; i <= pointNum; i++)
            for(int j = 0; j <= pointNum; j++)
                matrix[i][j] = INF;

        for(int d = 0; d < (1 << MAXPOINT); d++)
            dp[d] = -1;

        for(int r = 1; r <= roadNum; r++) {
            // get road information
            cin >> x >> y >> len;

            // each road must walk at least one time
            total += len;

            // calculate each point connect how many road
            pointInfo[x]++;
            pointInfo[y]++;

            // save the minimize one int the matrix
            matrix[x][y] = min(matrix[x][y], len);
            matrix[y][x] = min(matrix[y][x], len);
        }

        // compute the minimize length of each one point to other points
        for(int k = 1; k <= pointNum; k++)
            for(int i = 1; i <= pointNum; i++)
                for(int j = 1; j <= pointNum; j++)
                    matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);

        // get the odd roads of point's information
        oddNum = 0;
        for(int p = 1; p <= pointNum; p++) {
            if(pointInfo[p] % 2 != 0) {
                odd[oddNum] = p;
                oddNum++;
            }
        }

        // output the final answer
        cout << total + build((1 << oddNum) - 1, oddNum) << endl;
    }

    return 0;
}