# JZOJ – 5459 密室

Time Limit : 1000ms
Memory Limit : 512MB

## Sample Input

3 3 2
1 0
0 1
0 0
1 3 1 1
1 2 1 0
2 3 1 1


## Sample Output

2


## Data Constraint

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

## 代码

#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;

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){
key[tot] = c;
to[tot] = b;
}

int main(){

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

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

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

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

}

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;

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;
}