http://www.topcoder.com/stat?c=problem_statement&pm=10123&rd=13513&rm=299010&cr=8347577

一道挺有意思的题目，也蛮tricky的，我在写的时候就想偏了一点，虽然过了sample数据，最后还是被人cha了 :(

题目从经典的过桥问题派生过来，只是限制更多了：

• 只有一张地图，所以全部人过去之前每次要有若干人把图带回来
• 桥的承受重量有上限
• 每次过桥的一个小组里面，每个组员至少信赖一个其他组员（一个人过桥时不受这个限制）、
• 求最短的过桥时间（一组人过桥时间按最慢的那个人算）

我第一眼看去就是一个Bit DP，给的人数上限（13）也基本符合TC的习惯。但是写的时候想偏了。我假设除了最后一次，每次至少有两个人过桥，然后从中选一个人回来。这里有一个致命的逻辑错误。考虑3个人，相互之间都互相信赖的情况。3个人体重分别为3、3、6，而桥承受重量的上限为6。那么必须是首先两个体重3的人过去，一个人拿地图回来，然后体重6的人单独过去，另一个体重3的人回来，最后再两个体重3的人一起过桥。昨天晚上我还以为自己是超时挂了，和magicpig讨论时也没有发现自己逻辑上的错误。

因为可以出现一人过桥再一人回来的情况，DP在这里按我理解就不太适用了，因为情况会变得复杂（考虑一个人过桥然后又自己跑回来的情况）。这个和前几周在组里做的一个token nested replacement的情况有点类似，但那个显然要简单许多了。在这种情况下，BFS应该是一个合适的解法。

人的状态总共是2^13，考虑地图在左边还是右边再乘以2，总的时间复杂度是2^14。magicpig昨天提到的2^26的复杂度应该是可以简化的。因为知道了桥左边人头的情况，右边的可以相应的算出来。

对于每一个状态，有3个东西需要记录，地图在左还是在右，当前桥左边的人头状况，该状态与目标状态（人全在桥右，地图也在右）的距离。每次过桥时都是枚举可以过桥的人的所有组合。后面就是一个典型的BFS的PQ实现了。

附代码如下：

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define MAXN 13
#define INF 1000000000

class state {
public:
    int mp, mask, dist;
    state(int _mp, int _mask, int _dist) : mp(_mp), mask(_mask), dist(_dist) {};
    bool operator<(const state &rhs) const {
        return dist > rhs.dist;
    }
};

int n, bs, full, gt[1 << MAXN], mm[2][1 << MAXN];
vector<int> weight, tt;
vector<string> trust;
priority_queue <state> pq;

void init() {
    memset(gt, 0, sizeof(gt));
    gt[0] = INF;
    FOR(m,1,full) {
        int wtot = 0;
        REP(i,n) if (m & 1 << i) {
            wtot += weight[i];
            gt[m] = max(gt[m], tt[i]);
        }
        if (wtot > bs) gt[m] = INF;
        if (m & (m - 1)) {
            bool fl = true;
            REP(i,n) if (m & 1 << i) {
                int mk = false;
                REP(j,n) if ((m & 1 << j) && i != j && trust[i][j] == 'Y') {
                    mk = true;
                    break;
                }
                if (!mk) {
                    fl = false;
                    break;
                }
            }
            if (!fl) gt[m] = INF;
        }
    }
}

int doit() {
    memset(mm, 127, sizeof(mm));
    mm[0][full] = 0;
    pq.push(state(0, full, 0));
    while (!pq.empty()) {
        state cur = pq.top(); pq.pop();
        int dist = cur.dist, mp = cur.mp, mask = cur.mask;
        if (dist > mm[mp][mask]) continue;
        int s = mp == 0 ? mask : (mask ^ full);
        for (int m = s; m > 0; m = m - 1 & s) {
            if (dist + gt[m] < mm[1 - mp][mask ^ m]) {
                mm[1 - mp][mask ^ m] = dist + gt[m];
                pq.push(state(1 - mp, mask ^ m, mm[1 - mp][mask ^ m]));
            }
        }
    }
    return mm[1][0] < INF ? mm [1][0] : -1;
}

class CavePassage {
public:
    int minimalTime(vector<int> travelersWeights, vector<int> travelersTimes, vector<string> trustTable, int bridgeStrength)
    {
        n = travelersWeights.size();
        full = (1 << n) - 1;
        bs = bridgeStrength;
        weight = travelersWeights;
        tt = travelersTimes;
        trust = trustTable;

        init();
        return doit();
    }
};