{"id":217,"date":"2012-05-06T03:35:41","date_gmt":"2012-05-05T19:35:41","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=217"},"modified":"2012-05-15T00:01:59","modified_gmt":"2012-05-14T16:01:59","slug":"google-code-jam-2012-round-1b","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/google-code-jam-2012-round-1b\/","title":{"rendered":"Google Code Jam 2012 Round 1B"},"content":{"rendered":"<h3>Brief description: <\/h3>\n<p>A: \u4e8c\u5206\u7b54\u6848\u8d2a\u5fc3\u3002<br \/>\nB: \u4e24\u6b21 bfs();<br \/>\nC: \u3002\u5b50\u96c6\u5408\u95ee\u9898\uff0c\u95ee\u662f\u5426\u5b58\u5728\u4e24\u4e2a\u4e0d\u76f8\u4ea4\u7684\u5b50\u96c6\uff0c\u4f7f\u5f97\u5b83\u4eec\u7684\u548c\u76f8\u7b49 0w0\u3002\u3002<\/p>\n<p><!--more--><\/p>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **\/\r\n\r\n#include &lt;algorithm&gt;\r\n#include &lt;iostream&gt;\r\n#include &lt;iomanip&gt;\r\n#include &lt;sstream&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;cstdio&gt;\r\n#include &lt;string&gt;\r\n#include &lt;vector&gt;\r\n#include &lt;bitset&gt;\r\n#include &lt;queue&gt;\r\n#include &lt;stack&gt;\r\n#include &lt;cmath&gt;\r\n#include &lt;ctime&gt;\r\n#include &lt;list&gt;\r\n#include &lt;set&gt;\r\n#include &lt;map&gt;\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i&lt;int(n);++i)\r\n#define FOR(i, a, b) for (int i=int(a);i&lt;int(b);++i)\r\n#define DWN(i, b, a) for (int i=int(b-1);i&gt;=int(a);--i)\r\n#define REP_1(i, n) for (int i=1;i&lt;=int(n);++i)\r\n#define FOR_1(i, a, b) for (int i=int(a);i&lt;=int(b);++i)\r\n#define DWN_1(i, b, a) for (int i=int(b);i&gt;=int(a);--i)\r\n#define REP_C(i, n) for (int n____=int(n),i=0;i&lt;n____;++i)\r\n#define FOR_C(i, a, b) for (int b____=int(b),i=a;i&lt;b____;++i)\r\n#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i&gt;=a____;--i)\r\n#define REP_N(i, n) for (i=0;i&lt;int(n);++i)\r\n#define FOR_N(i, a, b) for (i=int(a);i&lt;int(b);++i)\r\n#define DWN_N(i, b, a) for (i=int(b-1);i&gt;=int(a);--i)\r\n#define REP_1_C(i, n) for (int n____=int(n),i=1;i&lt;=n____;++i)\r\n#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i&lt;=b____;++i)\r\n#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i&gt;=a____;--i)\r\n#define REP_1_N(i, n) for (i=1;i&lt;=int(n);++i)\r\n#define FOR_1_N(i, a, b) for (i=int(a);i&lt;=int(b);++i)\r\n#define DWN_1_N(i, b, a) for (i=int(b);i&gt;=int(a);--i)\r\n#define REP_C_N(i, n) for (n____=int(n),i=0;i&lt;n____;++i)\r\n#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i&lt;b____;++i)\r\n#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i&gt;=a____;--i)\r\n#define REP_1_C_N(i, n) for (n____=int(n),i=1;i&lt;=n____;++i)\r\n#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i&lt;=b____;++i)\r\n#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i&gt;=a____;--i)\r\n\r\n#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)\r\n#define DO(n) while(n--)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\n#define TO(i, a, b) int s_=a&lt;b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)\r\n#define TO_1(i, a, b) int s_=a&lt;b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)\r\n#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i&lt;j;++i,--j)\r\n#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i&lt;=j;++i,--j)\r\n#define REP_2(i, j, n, m) REP(i, n) REP(j, m)\r\n#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)\r\n\r\n#define ALL(A) A.begin(), A.end()\r\n#define LLA(A) A.rbegin(), A.rend()\r\n#define CPY(A, B) memcpy(A, B, sizeof(A))\r\n#define INS(A, P, B) A.insert(A.begin() + P, B)\r\n#define ERS(A, P) A.erase(A.begin() + P)\r\n#define BSC(A, X) find(ALL(A), X) \/\/ != A.end()\r\n#define CTN(T, x) (T.find(x) != T.end())\r\n#define SZ(A) int(A.size())\r\n#define PB push_back\r\n#define MP(A, B) make_pair(A, B)\r\n\r\n#define Rush int T____; RD(T____); DO(T____)\r\n#pragma comment(linker, &quot;\/STACK:36777216&quot;)\r\n\/\/#pragma GCC optimize (&quot;O2&quot;)\r\n#define Ruby system(&quot;ruby main.rb&quot;)\r\n#define Haskell system(&quot;runghc main.hs&quot;)\r\n#define Pascal system(&quot;fpc main.pas&quot;)\r\n\r\ntypedef long long LL;\r\ntypedef double DB;\r\ntypedef unsigned UINT;\r\ntypedef unsigned long long ULL;\r\n\r\ntypedef vector&lt;int&gt; VI;\r\ntypedef vector&lt;char&gt; VC;\r\ntypedef vector&lt;string&gt; VS;\r\ntypedef vector&lt;LL&gt; VL;\r\ntypedef vector&lt;DB&gt; VD;\r\ntypedef set&lt;int&gt; SI;\r\ntypedef set&lt;string&gt; SS;\r\ntypedef set&lt;LL&gt; SL;\r\ntypedef set&lt;DB&gt; SD;\r\ntypedef map&lt;int, int&gt; MII;\r\ntypedef map&lt;string, int&gt; MSI;\r\ntypedef map&lt;LL, int&gt; MLI;\r\ntypedef map&lt;DB, int&gt; MDI;\r\ntypedef map&lt;int, bool&gt; MIB;\r\ntypedef map&lt;string, bool&gt; MSB;\r\ntypedef map&lt;LL, bool&gt; MLB;\r\ntypedef map&lt;DB, bool&gt; MDB;\r\ntypedef pair&lt;int, int&gt; PII;\r\ntypedef pair&lt;int, bool&gt; PIB;\r\ntypedef vector&lt;PII&gt; VII;\r\ntypedef vector&lt;VI&gt; VVI;\r\ntypedef vector&lt;VII&gt; VVII;\r\ntypedef set&lt;PII&gt; SII;\r\ntypedef map&lt;PII, int&gt; MPIII;\r\ntypedef map&lt;PII, bool&gt; MPIIB;\r\n\r\n\/** I\/O Accelerator **\/\r\n\r\n\/* ... :&quot; We are I\/O Accelerator ... Use us at your own risk ;) ... &quot; .. *\/\r\n\r\ntemplate&lt;class T&gt; inline void RD(T &amp;);\r\ntemplate&lt;class T&gt; inline void OT(const T &amp;);\r\n\r\ninline int RD(){ int x; RD(x); return x;}\r\ntemplate&lt;class T&gt; inline T&amp; _RD(T &amp;x){ RD(x); return x;}\r\ninline void RC(char &amp;c){scanf(&quot; %c&quot;, &amp;c);}\r\ninline void RS(char *s){scanf(&quot;%s&quot;, s);}\r\n\r\ntemplate&lt;class T0, class T1&gt; inline void RD(T0 &amp;x0, T1 &amp;x1){RD(x0), RD(x1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2){RD(x0), RD(x1), RD(x2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3){RD(x0), RD(x1), RD(x2), RD(x3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5, T6 &amp;x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);}\r\ntemplate&lt;class T0, class T1&gt; inline void OT(T0 &amp;x0, T1 &amp;x1){OT(x0), OT(x1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void OT(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2){OT(x0), OT(x1), OT(x2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void OT(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3){OT(x0), OT(x1), OT(x2), OT(x3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void OT(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void OT(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void OT(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5, T6 &amp;x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}\r\n\r\ntemplate&lt;class T&gt; inline void RST(T &amp;A){memset(A, 0, sizeof(A));}\r\ntemplate&lt;class T0, class T1&gt; inline void RST(T0 &amp;A0, T1 &amp;A1){RST(A0), RST(A1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){RST(A0), RST(A1), RST(A2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){RST(A0), RST(A1), RST(A2), RST(A3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}\r\n\r\ntemplate&lt;class T&gt; inline void CLR(T &amp;A){A.clear();}\r\ntemplate&lt;class T0, class T1&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1){CLR(A0), CLR(A1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){CLR(A0), CLR(A1), CLR(A2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}\r\ntemplate&lt;class T&gt; inline void CLR(T &amp;A, int n){REP(i, n) CLR(A&#x5B;i]);}\r\ntemplate&lt;class T&gt; inline void FLC(T &amp;A, int x){memset(A, x, sizeof(A));}\r\ntemplate&lt;class T0, class T1&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, int x){FLC(A0, x), FLC(A1, x);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){FLC(A0), FLC(A1), FLC(A2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){FLC(A0), FLC(A1), FLC(A2), FLC(A3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);}\r\n\r\ntemplate&lt;class T&gt; inline void SRT(T &amp;A){sort(ALL(A));}\r\ntemplate&lt;class T, class C&gt; inline void SRT(T &amp;A, C B){sort(ALL(A), B);}\r\n\r\n\/** Add - On **\/\r\n\r\nconst int MOD = 1000000007;\r\nconst int INF = 0x3f3f3f3f;\r\nconst DB EPS = 1e-9;\r\nconst DB OO = 1e15;\r\nconst DB PI = 3.14159265358979323846264;\/\/M_PI;\r\n\r\n\/\/ &lt;&lt;= ` 0. Daily Use .,\r\n\r\ntemplate&lt;class T&gt; inline void checkMin(T &amp;a,const T b){if (b&lt;a) a=b;}\r\ntemplate&lt;class T&gt; inline void checkMax(T &amp;a,const T b){if (b&gt;a) a=b;}\r\ntemplate &lt;class T, class C&gt; inline void checkMin(T&amp; a, const T b, C c){if (c(b,a)) a = b;}\r\ntemplate &lt;class T, class C&gt; inline void checkMax(T&amp; a, const T b, C c){if (c(a,b)) a = b;}\r\ntemplate&lt;class T&gt; inline T min(T a, T b, T c){return min(min(a, b), c);}\r\ntemplate&lt;class T&gt; inline T max(T a, T b, T c){return max(max(a, b), c);}\r\ntemplate&lt;class T&gt; inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}\r\ntemplate&lt;class T&gt; inline T max(T a, T b, T c, T d){return max(min(a, b), max(c, d));}\r\ntemplate&lt;class T&gt; inline T sqr(T a){return a*a;}\r\ntemplate&lt;class T&gt; inline T cub(T a){return a*a*a;}\r\nint Ceil(int x, int y){return (x - 1) \/ y + 1;}\r\n\r\n\/\/ &lt;&lt;= ` 1. Bitwise Operation .,\r\n\r\ninline bool _1(int x, int i){return x &amp; 1&lt;&lt;i;}\r\ninline int _1(int i){return 1&lt;&lt;i;}\r\ninline int _U(int i){return _1(i) - 1;};\r\n\r\ninline int count_bits(int x){\r\n    x = (x &amp; 0x55555555) + ((x &amp; 0xaaaaaaaa) &gt;&gt; 1);\r\n    x = (x &amp; 0x33333333) + ((x &amp; 0xcccccccc) &gt;&gt; 2);\r\n    x = (x &amp; 0x0f0f0f0f) + ((x &amp; 0xf0f0f0f0) &gt;&gt; 4);\r\n    x = (x &amp; 0x00ff00ff) + ((x &amp; 0xff00ff00) &gt;&gt; 8);\r\n    x = (x &amp; 0x0000ffff) + ((x &amp; 0xffff0000) &gt;&gt; 16);\r\n    return x;\r\n}\r\n\r\ntemplate&lt;class T&gt; inline T low_bit(T x) {\r\n    return x &amp; -x;\r\n}\r\n\r\ntemplate&lt;class T&gt; inline T high_bit(T x) {\r\n    T p = low_bit(x);\r\n    while (p != x) x -= p, p = low_bit(x);\r\n    return p;\r\n}\r\n\r\n\/\/ &lt;&lt;= ' 0. I\/O Accelerator interface .,\r\n\r\ntemplate&lt;class T&gt; inline void RD(T &amp;x){\r\n    \/\/cin &gt;&gt; x;\r\n    scanf(&quot;%d&quot;, &amp;x);\r\n    \/\/char c; for (c = getchar(); c &lt; '0'; c = getchar()); x = c - '0'; for (c = getchar(); c &gt;= '0'; c = getchar()) x = x * 10 + c - '0';\r\n    \/\/char c; c = getchar(); x = c - '0'; for (c = getchar(); c &gt;= '0'; c = getchar()) x = x * 10 + c - '0';\r\n}\r\n\r\nint ____Case;\r\ntemplate&lt;class T&gt; inline void OT(const T &amp;x){\r\n    \/\/printf(&quot;Case #%d: &quot;, ++____Case);\r\n    printf(&quot;%d&quot;, x);\r\n    puts(&quot;&quot;);\r\n}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int dx&#x5B;] = {0, 1, 0, -1};\r\nconst int dy&#x5B;] = {1, 0, -1, 0};\r\nconst int N = 109;\r\n\r\nint bottom&#x5B;N]&#x5B;N], upper&#x5B;N]&#x5B;N];\r\nint h, n, m;\r\n\r\ninline int water_leval(int t){\r\n    return h - t;\r\n}\r\n\r\nstruct state{\r\n    int x, y, t;\r\n\r\n    state(int _x, int _y, int _t):x(_x), y(_y), t(_t){}\r\n\r\n    int speed(){\r\n        if (water_leval(t) - bottom&#x5B;x]&#x5B;y] &gt;= 20) return 10;\r\n        return 100;\r\n    }\r\n\r\n    friend bool operator &lt;(const state&amp; lhs, const state&amp; rhs){\r\n        return lhs.t &lt; rhs.t;\r\n    }\r\n    friend bool operator &gt;(const state&amp; lhs, const state&amp; rhs){\r\n        return lhs.t &gt; rhs.t;\r\n    }\r\n};\r\n\r\npriority_queue&lt;state, vector&lt;state&gt;, greater&lt;state&gt; &gt; Q;\r\nvector&lt;PII&gt; _Q; int head;\r\n\r\ninline bool legal(int x, int y){\r\n    return upper&#x5B;x]&#x5B;y] - bottom&#x5B;x]&#x5B;y] &gt;= 50;\r\n}\r\n\r\ninline bool link(int x, int y, int xx, int yy){\r\n    return legal(xx, yy) &amp;&amp; upper&#x5B;xx]&#x5B;yy] - bottom&#x5B;x]&#x5B;y] &gt;= 50 &amp;&amp; upper&#x5B;x]&#x5B;y] - bottom&#x5B;xx]&#x5B;yy] &gt;= 50;\r\n}\r\n\r\nint open_time(int x, int y, int xx, int yy, int t){\r\n    if (!legal(xx, yy)) return INF;\r\n\r\n    return max(\r\n        (upper&#x5B;xx]&#x5B;yy] - bottom&#x5B;x]&#x5B;y] &gt;= 50) ? (water_leval(t) - upper&#x5B;xx]&#x5B;yy] + 50) : INF,\r\n            (upper&#x5B;x]&#x5B;y] - bottom&#x5B;xx]&#x5B;yy] &gt;= 50) ? (water_leval(t) - upper&#x5B;x]&#x5B;y] + 50) : INF, 0);\r\n\r\n}\r\n\r\n\r\nvoid init(){\r\n    RD(h, n, m); RST(bottom, upper);\r\n    REP_2_1(i, j, n, m) RD(upper&#x5B;i]&#x5B;j]);\r\n    REP_2_1(i, j, n, m) RD(bottom&#x5B;i]&#x5B;j]);\r\n    CLR(_Q); while (!Q.empty()) Q.pop();\r\n}\r\n\r\n\r\nbool C&#x5B;N]&#x5B;N];\r\n\r\nvoid bfs1(){\r\n\r\n    _Q.PB(MP(1, 1)); RST(C); C&#x5B;1]&#x5B;1] = true; head = 0;\r\n\r\n    while (head &lt; SZ(_Q)){\r\n\r\n        int x = _Q&#x5B;head].first, y = _Q&#x5B;head].second;\r\n\r\n        REP(i, 4){\r\n            int xx = x + dx&#x5B;i], yy = y + dy&#x5B;i];\r\n            if (!C&#x5B;xx]&#x5B;yy] &amp;&amp; link(x, y, xx, yy)){\r\n                if (!open_time(x, y, xx, yy, 0)){\r\n                    _Q.PB(MP(xx, yy));\r\n                    C&#x5B;xx]&#x5B;yy] = true;\r\n                }\r\n            }\r\n        }\r\n\r\n        ++head;\r\n    }\r\n}\r\n\r\n\r\n\r\nvoid bfs2(){\r\n\r\n    RST(C); REP(i, SZ(_Q)) Q.push(state(_Q&#x5B;i].first, _Q&#x5B;i].second, 0));\r\n\r\n    while (!Q.empty()){\r\n\r\n        state u = Q.top(); Q.pop();\r\n        if (C&#x5B;u.x]&#x5B;u.y]) continue;\r\n        C&#x5B;u.x]&#x5B;u.y] = true;\r\n\r\n        if (u.x == n &amp;&amp; u.y == m){\r\n            printf(&quot;%.1lf\\n&quot;, (DB) u.t \/ 10);\r\n            return;\r\n        }\r\n\r\n        REP(i, 4){\r\n\r\n            int xx = u.x + dx&#x5B;i], yy = u.y + dy&#x5B;i];\r\n\r\n            if (C&#x5B;xx]&#x5B;yy]) continue;\r\n\r\n            if (link(u.x, u.y, xx, yy)){\r\n                int tt = open_time(u.x, u.y, xx, yy, u.t);\r\n                u.t += tt;\r\n                Q.push( state(xx, yy, u.t + u.speed()));\r\n                u.t -= tt;\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n    \/\/freopen(&quot;B-large-practice.in&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;A-large.in&quot;, &quot;r&quot;, stdin);\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n\r\n    Rush{\r\n        printf(&quot;Case #%d: &quot;, ++____Case);\r\n        init(); bfs1(); bfs2();\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: A: \u4e8c\u5206\u7b54\u6848\u8d2a\u5fc3\u3002 B: \u4e24\u6b21 bfs(); C: \u3002\u5b50\u96c6\u5408\u95ee\u9898\uff0c\u95ee\u662f\u5426\u5b58\u5728\u4e24\u4e2a\u4e0d\u76f8\u4ea4\u7684\u5b50\u96c6\uff0c\u4f7f\u5f97\u5b83\u4eec\u7684\u548c\u76f8\u7b49 0w0\u3002\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[67],"tags":[],"class_list":["post-217","post","type-post","status-publish","format-standard","hentry","category-google-code-jam"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-3v","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/217","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=217"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/217\/revisions"}],"predecessor-version":[{"id":219,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/217\/revisions\/219"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=217"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=217"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}