Nosknah 的宝藏

Problem

Source: BSOJ 3031

Description

Nosknah 是 XMYZ 高中部默默无闻的一员，他有一个在 2009 年 NOIP 时一日成名的哥哥 Hankson，Nosknah 喜欢收集宝藏，他知道学校的后花园里面藏有 $P$ 个珍品。经过严密调查，他知道后花园分成了 $N$ 块区域，由 $M$ 条无向路径连接。

Nosknah要从 1 区域出发，捡完所有的宝藏后从 $N$ 区域离开。Nosknah 没有 Hankson 那么聪明，他现在求助你：他最短走多远就能捡完宝藏并离开？为了简化问题，我们假设 Nosknah 拿走珍品不需要花费任何时间。

数据范围：

对 $30 \%$ 的数据，$1 \leq N \leq 10，1 \leq M \leq 100，0 \leq P \leq 5$；
对 $100 \%$ 的数据，$1 \leq N \leq 200，1 \leq M \leq 10,000，0 \leq P \leq 12$，道路长度不超过 $1,000,000,000$；
其中，$N$、$M$、$P$、道路长度均为整数。

Input

第 1 行两个整数 $N$、$M$。　

第 2 行到第 $M+1$ 行，每行三个整数 $x$、$y$、$w$，表示 $x$、$y$ 号区域（$1 \leq x, y \leq N$）间有一条道路，该道路长度为 $w$。

第 $M+2$ 行一个整数 $P$。

第 $M+3$ 行有用空格隔开的 $P$ 个整数，第 $i$ 个数 $P_i$ 代表第 $i$ 个珍品藏在第 $P_i$ 个区域。

Output

第 1 行为一个整数，为 Nosknah 拿到所有宝藏并离开的所需走过的最短道路长度。如无法全部捡到或者无法离开，输出 -1。

Sample Input

Sample Output

Output Details

直接按 $1 \rightarrow 2 \rightarrow 3$ 路线走，可以拿走 2 区域的珍品，并以最短时间 7 到达 3 区域（即 $N$ 号区域）。

Solution

先用利用 Floyd 算法计算多源最短路，时间复杂度为 $O(n^3)$。

然后状态压缩记忆化搜索，设当前状态为 $A$：

将第 $k$ 个珍品捡到：$A=A+(1«(k-1))$；
检查是否捡过第 $k$ 个物品：bool check $= A \& (1«(k-1))$。

记忆化搜索的一般步骤伪代码：

Procedure Dp(status: int)
    if(已经计算过 status 的最优值) return 最优值       
    else  扩展后续状态，并计算 status 最优值  
    记录 status 最优值  
    return 最优值

Code

Github (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <deque>
using namespace std;

typedef long long LL;

const LL inf = 1LL << 60;
LL n, m, P, a[15];
LL f[205][5005], map[205][205], Ans = inf;

void Init() {
    LL z, x, y, h;

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) map[i][j] = inf;

    for(int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        map[x][y] = map[y][x] = min(map[x][y], z);
    }

    cin >> P;
    h = 1 << P;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= h; j++) f[i][j] = inf;

    for(int i = 1; i <= P; i++) cin >> a[i];
}

void Floyed() {
    for(int k = 1; k <= n; k++) {
        map[k][k] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(i != j && map[i][j] > map[i][k] + map[k][j])
                    map[i][j] = map[i][k] + map[k][j];
    }
}

int Check() {
    if(map[1][n] == inf)return 0;

    for(int i = 1; i <= P; i++)
        for(int j = 1; j <= n; j++)
            if(map[a[i]][j] == inf) return 0;

    return 1;
}

void Dfs(LL x, LL dis, LL A) {
    if(f[x][A] > dis) f[x][A] = dis;
    else return;

    if(A == ((1<<P) - 1)) {
        Ans = min(Ans, dis + map[x][n]);
        return;
    }

    for(int i = 1; i <= P; i++)
        if(!(A & (1<<(i-1))))
            Dfs(a[i], dis + map[x][a[i]], A | (1<<(i-1)));
}

int main() {
    Init();
    Floyed();
    if(Check()) {
        Dfs(1, 0, 0);
        cout << Ans << endl;
    }
    else printf("-1\n");
    return 0;
}

PREVIOUSSelection

NEXT游戏