JZOJ – 5459 密室

Time Limit : 1000ms
Memory Limit : 512MB

Description

小X 正困在一个密室里，他希望尽快逃出密室。
密室中有N 个房间，初始时，小X 在 $1$ 号房间，而出口在 $N$ 号房间。
密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间 $X$ 到房间 $Y$ 的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。
然而，通过密室的传送门需要耗费大量的时间，因此，小X 希望通过尽可能少的传送门到达出口，你能告诉小X 这个数值吗？
另外，小X 有可能不能逃出这个密室，如果是这样，请输出”No Solution”。

Input

第一行三个整数 $N$, $M$, $K$，分别表示房间的数量、传送门的数量以及钥匙的种类数。
接下来 $N$ 行，每行 $K$ 个 $0$ 或 $1$ ，若第 $i$ 个数为 $1$ ，则表示该房间内有第 $i$ 种钥匙，若第 $i$ 个数为 $0$ ，则表示该房间内没有第 $i$ 种钥匙。
接下来 $M$ 行，每行先读入两个整数 $X$, $Y$ ，表示该传送门是建立在 $X$ 号房间，通向 $Y$ 号房间的，再读入 $K$ 个 $0$ 或 $1$ ，若第 $i$ 个数为 $1$ ，则表示通过该传送门需要 $i$ 种钥匙，若第 $i$ 个数为 $0$ ，则表示通过该传送门不需要第i 种钥匙。

Output

输出一行一个“No Solution”，或一个整数，表示最少通过的传送门数

Sample Input

Sample Output

Data Constraint

n <= 5000, m <= 6000, k <= 10

解题思路

如果不考虑钥匙，那么可以直接考虑最短路，一个传送门可以看做一条边，但是我们发现边权始终为1， bfs即可。

但是，本题中添加了钥匙的限制条件。但是我们注意到 $k$ 的值非常小，我们可以考虑在bfs的过程中加上一个维度通过状态压缩表示你当前拥有了哪些钥匙。

在bfs的过程中，如果你拥有开启该传送门的钥匙，那么就可以通过这条边，并且获得令一个房间的钥匙。否则继续查找其他状态。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
const int MAXN = 5000 + 10;
const int MAXM = 6000 + 10;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int n, m, k;
int room[MAXN];
int Head[MAXN], Next[MAXM], to[MAXM], key[MAXM], tot = 1;

int dis[MAXN][1200];

inline void add(int a, int b, int c){
    Next[tot] = Head[a];
    key[tot] = c;
    to[tot] = b;
    Head[a] = tot++;
}

int main(){

    freopen("room.in", "r", stdin);
    freopen("room.out", "w", stdout);

    n = read();
    m = read();
    k = read();

    for(register int i=1; i<=n; i++){
        for(register int j=0; j<k; j++)
            room[i] += read() << j;
    }

    for(register int i=1; i<=m; i++){
        int x = read();
        int y = read();
        int z = 0;

        for(register int j=0; j<k; j++)
            z += read() << j;

        add(x, y, z);
    }

    queue <pair<int, int> > que;
    while(!que.empty())
        que.pop();

    memset(dis, 0x3f, sizeof(dis));
    int ans = 0x3f3f3f3f;
    que.push(make_pair(1, room[1]));
    dis[1][room[1]] = 0;

    while(!que.empty()){
        pair <int, int> pos = que.front();
        que.pop();

        int now = pos.first;

        for(register int i=Head[now]; i; i=Next[i]){
            int v = to[i];
            if((pos.second & key[i]) == key[i] && dis[now][pos.second] + 1 < dis[v][pos.second | room[v]]){
                dis[v][pos.second | room[v]] = dis[now][pos.second] + 1;
                if(v == n){
                    ans = min(ans, dis[v][pos.second | room[v]]);
                }
                que.push(make_pair(v, pos.second | room[v]));
            }
        }
    }

    if(ans == 0x3f3f3f3f){
        printf("No Solution");
    }else{
        printf("%d\n", ans);
    }
    return 0;
}

[题解] JZOJ – 5459 密室

BLOG