洛谷 P4011 孤島營救問題【最短路+分層圖】

題外話：昨夜腦子昏沉，今早一調試就過了...錯誤有：我忘記還有墻直接穿墻過...memset初始化INF用錯了數...然后手殘敲錯一個狀態一直過不了樣例...要是這狀態去比賽我簡直完了......orz

題目鏈接：https://www.luogu.org/problemnew/show/P4011

?

輸入輸出樣例

輸入樣例#1：

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1

輸出樣例#1：

14

?

題解：分層圖最短路問題。最多就10類門，一看就是狀態壓縮最大空間 (1<<11)-1 ，很友好...d[i][sta]表示到點i，狀態為sta的最短路長度(sta就是到i點前所持有的鑰匙的狀態)。

代碼：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#define CLR(a, b) memset((a), (b), sizeof((a)))
using namespace std;
const int N = 110;
const int states = 1<<11;
const int INF = 0x3f3f3f3f;

int d[N][states], vis[N][states];
int id[N][N];
int key[N];     //key[i]:i點有哪些鑰匙（狀態）
int mp[N][N];   //mp[i][j]:i到j有哪類門
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int n, m, p;
struct qnode{
    int v;
    int x;//狀態
    qnode(int _v=0,int _x=0):v(_v),x(_x){}
};
bool SPFA(int st, int ed) {
    CLR(vis, 0);
    CLR(d, INF);
    d[st][0] = 0;
    queue<qnode> q;
    while(!q.empty()) q.pop();
    q.push(qnode(st, 0));
    while(!q.empty()) {
        qnode t = q.front(); q.pop();
        int u = t.v;
        int sta = t.x;
        vis[u][sta] = false;

        if(key[u]) sta |= key[u];
        for(int i = 0; i < 4; i++) {
            int x = (u+m-1)/m + dx[i];
            int y = (u%m?u%m:m) + dy[i];

            if(x < 1 || x > n || y < 1 || y > m) continue;
            int v = id[x][y];
            //不是墻 并且 有對應鑰匙 或者沒有門。
            if(mp[u][v]!=0 && ( (sta&(1<<mp[u][v])) || mp[u][v]==-1)) {
                if(d[v][sta] > d[u][t.x] + 1) {
                    d[v][sta] = d[u][t.x] + 1;
                    if(!vis[v][sta]) {
                        vis[v][sta] = true;
                        q.push(qnode(v, sta));
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < states; ++i) ans = min(ans, d[ed][i]);
    if(ans == INF) puts("-1");
    else printf("%d\n", ans);
}
int main() {
    int i, j, k, x1, y1, x2, y2, q, sum;
    scanf("%d%d%d", &n, &m, &p);//行,列,門和墻的總數

    int cnt = 0;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j) id[i][j] = ++cnt;

    CLR(mp, -1);
    scanf("%d", &k);//門和墻總數
    for(i = 1; i <= k; ++i) {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &q);
        int id1 = id[x1][y1];
        int id2 = id[x2][y2];
        mp[id1][id2] = mp[id2][id1] = q;
    }
    scanf("%d", &sum);//鑰匙總數
    for(i = 1; i <= sum; ++i) {
        scanf("%d%d%d", &x1, &y1, &q);
        key[id[x1][y1]] |= (1<<q);
    }
    SPFA(1, n*m);
    return 0;
}

?