HDUOJ 5418 Victor and World -（状压DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5418

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <map>
#include <algorithm>
#include <stack>
#include <cstring>
#include <vector>
using namespace std;inline int read_int() {
     int a; scanf("%d", &a); return a; }const int INF = 0x3fffffff;
#define N 16
int cost[N][N];
int dp[N][1 << N]; // dp[i][S] denotes: cur_pos is i, visited set is Sint main() {
    //std::ios::sync_with_stdio(false);//std::cin.tie(NULL);int T = read_int();while (T--){
    for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++)cost[i][j] = INF;for (int j = 0; j < (1 << N); j++)dp[i][j] = INF;}dp[0][1] = 0; // startconst int n = read_int(), m = read_int();for (int i = 0; i < m; i++) {
    int u = read_int(), v = read_int(), w = read_int();cost[u - 1][v - 1] = min(w, cost[u - 1][v - 1]);cost[v - 1][u - 1] = min(w, cost[v - 1][u - 1]);}// floydfor (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);// dp[j][S U {j}] = min_i(dp[i][S] + cost[i][j]);int S = 1;for (; S < (1 << n); S++) {
    for (int j = 0; j < n; j++) {
    // enumerate i in S, with path to jfor (int i = 0; i < n; i++)if (i != j && S&(1 << i) && cost[i][j] != INF)dp[j][S | (1 << j)] = min(dp[j][S | (1 << j)],dp[i][S] + cost[i][j]);}}printf("%d\n", dp[0][(1 << n) - 1]);}//system("pause");return 0;
}