深圳企业建站模板,网站提取规则怎么设置,旅游网站系统建设方案,沂水网站制作题外话#xff1a;昨夜脑子昏沉#xff0c;今早一调试就过了...错误有#xff1a;我忘记还有墙直接穿墙过...memset初始化INF用错了数...然后手残敲错一个状态一直过不了样例...要是这状态去比赛我简直完了......orz 题目链接#xff1a;https://www.luogu.org/problemnew/… 题外话昨夜脑子昏沉今早一调试就过了...错误有我忘记还有墙直接穿墙过...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类门一看就是状态压缩最大空间 (111)-1 很友好...d[i][sta]表示到点i状态为sta的最短路长度(sta就是到i点前所持有的钥匙的状态)。 代码 1 #include cstdio2 #include vector3 #include algorithm4 #include queue5 #include cstring6 #define CLR(a, b) memset((a), (b), sizeof((a)))7 using namespace std;8 const int N 110;9 const int states 111;
10 const int INF 0x3f3f3f3f;
11
12 int d[N][states], vis[N][states];
13 int id[N][N];
14 int key[N]; //key[i]:i点有哪些钥匙状态
15 int mp[N][N]; //mp[i][j]:i到j有哪类门
16 int dx[] {1, 0, -1, 0};
17 int dy[] {0, 1, 0, -1};
18 int n, m, p;
19 struct qnode{
20 int v;
21 int x;//状态
22 qnode(int _v0,int _x0):v(_v),x(_x){}
23 };
24 bool SPFA(int st, int ed) {
25 CLR(vis, 0);
26 CLR(d, INF);
27 d[st][0] 0;
28 queueqnode q;
29 while(!q.empty()) q.pop();
30 q.push(qnode(st, 0));
31 while(!q.empty()) {
32 qnode t q.front(); q.pop();
33 int u t.v;
34 int sta t.x;
35 vis[u][sta] false;
36
37 if(key[u]) sta | key[u];
38 for(int i 0; i 4; i) {
39 int x (um-1)/m dx[i];
40 int y (u%m?u%m:m) dy[i];
41
42 if(x 1 || x n || y 1 || y m) continue;
43 int v id[x][y];
44 //不是墙 并且 有对应钥匙 或者没有门。
45 if(mp[u][v]!0 ( (sta(1mp[u][v])) || mp[u][v]-1)) {
46 if(d[v][sta] d[u][t.x] 1) {
47 d[v][sta] d[u][t.x] 1;
48 if(!vis[v][sta]) {
49 vis[v][sta] true;
50 q.push(qnode(v, sta));
51 }
52 }
53 }
54 }
55 }
56 int ans INF;
57 for(int i 0; i states; i) ans min(ans, d[ed][i]);
58 if(ans INF) puts(-1);
59 else printf(%d\n, ans);
60 }
61 int main() {
62 int i, j, k, x1, y1, x2, y2, q, sum;
63 scanf(%d%d%d, n, m, p);//行,列,门和墙的总数
64
65 int cnt 0;
66 for(i 1; i n; i)
67 for(j 1; j m; j) id[i][j] cnt;
68
69 CLR(mp, -1);
70 scanf(%d, k);//门和墙总数
71 for(i 1; i k; i) {
72 scanf(%d%d%d%d%d, x1, y1, x2, y2, q);
73 int id1 id[x1][y1];
74 int id2 id[x2][y2];
75 mp[id1][id2] mp[id2][id1] q;
76 }
77 scanf(%d, sum);//钥匙总数
78 for(i 1; i sum; i) {
79 scanf(%d%d%d, x1, y1, q);
80 key[id[x1][y1]] | (1q);
81 }
82 SPFA(1, n*m);
83 return 0;
84 } View Code 转载于:https://www.cnblogs.com/GraceSkyer/p/9022978.html
