{"id":264,"date":"2010-05-29T10:53:00","date_gmt":"2010-05-29T02:53:00","guid":{"rendered":"http:\/\/localhost\/?p=264"},"modified":"2010-05-29T10:53:00","modified_gmt":"2010-05-29T02:53:00","slug":"beijing2006_wolf_caught_a_rabbit","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=264","title":{"rendered":"[BeiJing2006]\u72fc\u6293\u5154\u5b50"},"content":{"rendered":"\n<p>[BeiJing2006]\u72fc\u6293\u5154\u5b50<\/p>\n<p>Time Limit:15000MS&#160; Memory Limit:165536K<br \/>Total Submit:762 Accepted:164 <br \/>Case Time Limit:4000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u73b0\u5728\u5c0f\u670b\u53cb\u4eec\u6700\u559c\u6b22\u7684&quot;\u559c\u7f8a\u7f8a\u4e0e\u7070\u592a\u72fc&quot;,\u8bdd\u8bf4\u7070\u592a\u72fc\u6293\u7f8a\u4e0d\u5230\uff0c\u4f46\u6293\u5154\u5b50\u8fd8\u662f\u6bd4\u8f83\u5728\u884c\u7684\uff0c\u800c\u4e14\u73b0\u5728\u7684\u5154\u5b50\u8fd8\u6bd4\u8f83\u7b28\uff0c\u5b83\u4eec\u53ea\u6709\u4e24\u4e2a\u7a9d\uff0c\u73b0\u5728\u4f60\u505a\u4e3a\u72fc\u738b\uff0c\u9762\u5bf9 \u4e0b\u9762\u8fd9\u6837\u4e00\u4e2a\u7f51\u683c\u7684\u5730\u5f62\uff1a <\/p>\n<p><img decoding=\"async\" src=\"http:\/\/61.187.179.132:8080\/JudgeOnline\/images\/1001.jpg\" \/> <br \/>\u5de6\u4e0a\u89d2\u70b9\u4e3a(1,1),\u53f3\u4e0b\u89d2\u70b9\u4e3a(N,M)(\u4e0a\u56fe\u4e2dN=4,M=5).\u6709\u4ee5\u4e0b\u4e09\u79cd\u7c7b\u578b\u7684\u9053\u8def <br \/>1:(x,y)&lt;==&gt;(x+1,y) <br \/>2:(x,y)&lt;==&gt;(x,y+1) <br \/>3:(x,y)&lt;==&gt;(x+1,y+1) <br \/>\u9053\u8def\u4e0a\u7684\u6743\u503c\u8868\u793a\u8fd9\u6761\u8def\u4e0a\u6700\u591a\u80fd\u591f\u901a\u8fc7\u7684\u5154\u5b50\u6570\uff0c\u9053\u8def\u662f\u65e0\u5411\u7684. <br \/>\u5de6\u4e0a\u89d2\u548c\u53f3\u4e0b\u89d2\u4e3a\u5154\u5b50\u7684\u4e24\u4e2a\u7a9d\uff0c\u5f00\u59cb\u65f6\u6240\u6709\u7684\u5154\u5b50\u90fd\u805a\u96c6\u5728\u5de6\u4e0a\u89d2(1,1)\u7684\u7a9d\u91cc\uff0c\u73b0\u5728\u5b83\u4eec\u8981\u8dd1\u5230\u53f3\u4e0b\u89e3(N,M)\u7684\u7a9d\u4e2d\u53bb\uff0c\u72fc\u738b\u5f00\u59cb\u4f0f\u51fb\u8fd9\u4e9b\u5154 \u5b50.\u5f53\u7136\u4e3a\u4e86\u4fdd\u9669\u8d77\u89c1\uff0c\u5982\u679c\u4e00\u6761\u9053\u8def\u4e0a\u6700\u591a\u901a\u8fc7\u7684\u5154\u5b50\u6570\u4e3aK\uff0c\u72fc\u738b\u9700\u8981\u5b89\u6392\u540c\u6837\u6570\u91cf\u7684K\u53ea\u72fc\uff0c\u624d\u80fd\u5b8c\u5168\u5c01\u9501\u8fd9\u6761\u9053\u8def\uff0c\u4f60\u9700\u8981\u5e2e\u52a9\u72fc\u738b\u5b89\u6392\u4e00\u4e2a\u4f0f\u51fb\u65b9\u6848\uff0c\u4f7f \u5f97\u5728\u5c06\u5154\u5b50\u4e00\u7f51\u6253\u5c3d\u7684\u524d\u63d0\u4e0b\uff0c\u53c2\u4e0e\u7684\u72fc\u7684\u6570\u91cf\u8981\u6700\u5c0f\u3002\u56e0\u4e3a\u72fc\u8fd8\u8981\u53bb\u627e\u559c\u7f8a\u7f8a\u9ebb\u70e6. <\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c\u4e00\u884c\u4e3aN,M.\u8868\u793a\u7f51\u683c\u7684\u5927\u5c0f\uff0cN,M\u5747\u5c0f\u4e8e\u7b49\u4e8e1000.\u63a5\u4e0b\u6765\u5206\u4e09\u90e8\u5206 <br \/>\u7b2c\u4e00\u90e8\u5206\u5171N\u884c\uff0c\u6bcf\u884cM-1\u4e2a\u6570\uff0c\u8868\u793a\u6a2a\u5411\u9053\u8def\u7684\u6743\u503c. <br \/>\u7b2c\u4e8c\u90e8\u5206\u5171N-1\u884c\uff0c\u6bcf\u884cM\u4e2a\u6570\uff0c\u8868\u793a\u7eb5\u5411\u9053\u8def\u7684\u6743\u503c. <br \/>\u7b2c\u4e09\u90e8\u5206\u5171N-1\u884c\uff0c\u6bcf\u884cM-1\u4e2a\u6570\uff0c\u8868\u793a\u659c\u5411\u9053\u8def\u7684\u6743\u503c. <br \/>\u8f93\u5165\u6587\u4ef6\u4fdd\u8bc1\u4e0d\u8d85\u8fc710M <\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u53c2\u4e0e\u4f0f\u51fb\u7684\u72fc\u7684\u6700\u5c0f\u6570\u91cf. <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>3 4<br \/>5 6 4<br \/>4 3 1<br \/>7 5 3<br \/>5 6 7 8<br \/>8 7 6 5<br \/>5 5 5<br \/>6 6 6<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>14<\/p>\n<p><strong>Source<br \/>\u8fd9\u9898\u4e00\u770b\u5c31\u662f\u6700\u5c0f\u5272\u95ee\u9898\uff0c\u4f46\u8303\u56f4\u600e\u4e48\u8fd9\u4e48\u5927\u56e7\u3002\u3002\u3002\u540e\u6765\u770b\u4e86\u5468\u51ac\u795e\u725b\u7684\u8bba\u6587(2008\u5e74\u7684\u90a3\u4e2a)\u624d\u77e5\u9053\u539f\u6765\u5e73\u9762\u56fe\u7684\u6700\u5c0f\u5272\u7b49\u4e8e\u5bf9\u5076\u56fe\u7684\u6700\u77ed\u8def\u56e7\u3002\u3002\u6784\u56fe\u5f88\u9ebb\u70e6\uff0c\u641e\u5f97\u6211\u7d2f\u6b7b\u56e7\u3002\u3002<br \/><\/strong><\/p>\n<p>#include&lt;cstdio&gt;<br \/>#include&lt;vector&gt;<br \/>#include&lt;queue&gt;<br \/>#include&lt;iostream&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>#define pb push_back<br \/>#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)<br \/>using namespace std;<br \/>const int maxn=1000,maxv=maxn*maxn*2,inf=~0U&gt;&gt;2;<br \/>int n,m,vs,vt,v;<br \/>int Node[maxn][maxn][2];<br \/>int Dist[maxv];<br \/>struct Edge<br \/>{<br \/>    int t,c;<br \/>    Edge(int _t,int _c):t(_t),c(_c){}<br \/>};<br \/>struct State<br \/>{<br \/>    int p,c;<br \/>    State(int _p,int _c):p(_p),c(_c){}<br \/>    bool operator&lt;(const State&amp;o)const<br \/>    {<br \/>        return c&gt;o.c;<br \/>    }<br \/>};<br \/>vector&lt;Edge&gt; E[maxv];<br \/>priority_queue&lt;State&gt; Q;<br \/>typedef vector&lt;Edge&gt;::iterator eit;<br \/>int Dijstra()<br \/>{<br \/>    rep(i,v)Dist[i]=inf;Q.push(State(vs,0));<br \/>    while(Q.size())<br \/>    {<br \/>        State t=Q.top();Q.pop();if(t.c&gt;Dist[t.p])continue;<br \/>        if(t.p==vt)return t.c;<br \/>        tr(e,E[t.p])<br \/>        {<br \/>            int ncost=t.c+e-&gt;c;<br \/>            if(ncost&lt;Dist[e-&gt;t])<br \/>            {<br \/>                Dist[e-&gt;t]=ncost;<br \/>                Q.push(State(e-&gt;t,ncost));<br \/>            }<br \/>        }<br \/>    }<br \/>}<br \/>void AddEdge(int s,int t,int c)<br \/>{<br \/>    E[s].pb(Edge(t,c));<br \/>    E[t].pb(Edge(s,c));<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    scanf(&quot;%d%d&quot;,&amp;n,&amp;m);v=0;<br \/>    rep(i,n-1)rep(j,m-1)rep(k,2)Node[i][j][k]=v++;<br \/>    vs=v++;vt=v++;int c;<br \/>    rep(j,m-1)scanf(&quot;%d&quot;,&amp;c),AddEdge(vs,Node[0][j][0],c);<br \/>    rep(i,n-2)rep(j,m-1)<br \/>    {<br \/>        scanf(&quot;%d&quot;,&amp;c);AddEdge(Node[i][j][1],Node[i+1][j][0],c);<br \/>    }<br \/>    rep(j,m-1)scanf(&quot;%d&quot;,&amp;c),AddEdge(Node[n-2][j][1],vt,c);<br \/>    rep(i,n-1)<br \/>    {<br \/>        scanf(&quot;%d&quot;,&amp;c);AddEdge(Node[i][0][1],vt,c);<br \/>        rep(j,m-2)<br \/>        {<br \/>            scanf(&quot;%d&quot;,&amp;c);AddEdge(Node[i][j+1][1],Node[i][j][0],c);<br \/>        }<br \/>        scanf(&quot;%d&quot;,&amp;c);AddEdge(vs,Node[i][m-2][0],c);<br \/>    }<br \/>    rep(i,n-1)<br \/>        rep(j,m-1)<br \/>        {<br \/>            scanf(&quot;%d&quot;,&amp;c);<br \/>            AddEdge(Node[i][j][0],Node[i][j][1],c);<br \/>        }<br \/>    printf(&quot;%dn&quot;,Dijstra());<br \/>}<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[BeiJing2006]\u72fc\u6293\u5154\u5b50 Time Limit:15000MS&#160; Memory Limit:165536KTotal Submit:762 Accepted:164 Case Time Limit:4000MS Description \u73b0\u5728\u5c0f\u670b\u53cb\u4eec\u6700\u559c\u6b22\u7684&quot;\u559c\u7f8a\u7f8a\u4e0e\u7070\u592a\u72fc&quot;,\u8bdd\u8bf4\u7070\u592a\u72fc\u6293\u7f8a\u4e0d\u5230\uff0c\u4f46\u6293\u5154\u5b50\u8fd8\u662f\u6bd4\u8f83\u5728\u884c\u7684\uff0c\u800c\u4e14\u73b0\u5728\u7684\u5154\u5b50\u8fd8\u6bd4\u8f83\u7b28\uff0c\u5b83\u4eec\u53ea\u6709\u4e24\u4e2a\u7a9d\uff0c\u73b0\u5728\u4f60\u505a\u4e3a\u72fc\u738b\uff0c\u9762\u5bf9 \u4e0b\u9762\u8fd9\u6837\u4e00\u4e2a\u7f51\u683c\u7684\u5730\u5f62\uff1a \u5de6\u4e0a\u89d2\u70b9\u4e3a(1,1),\u53f3\u4e0b\u89d2\u70b9\u4e3a(N,M)(\u4e0a\u56fe\u4e2dN=4,M=5).\u6709\u4ee5\u4e0b\u4e09\u79cd\u7c7b\u578b\u7684\u9053\u8def 1:(x,y)&lt;==&gt;(x+1,y) 2:(x,y)&lt;==&gt;(x,y+1) 3:(x,y)&lt;==&gt;(x+1,y+1) \u9053\u8def\u4e0a\u7684\u6743\u503c\u8868\u793a\u8fd9\u6761\u8def\u4e0a\u6700\u591a\u80fd\u591f\u901a\u8fc7\u7684\u5154\u5b50\u6570\uff0c\u9053\u8def\u662f\u65e0\u5411\u7684. \u5de6\u4e0a\u89d2\u548c\u53f3\u4e0b\u89d2\u4e3a\u5154\u5b50\u7684\u4e24\u4e2a\u7a9d\uff0c\u5f00\u59cb\u65f6\u6240\u6709\u7684\u5154\u5b50\u90fd\u805a\u96c6\u5728\u5de6\u4e0a\u89d2(1,1)\u7684\u7a9d\u91cc\uff0c\u73b0\u5728\u5b83\u4eec\u8981\u8dd1\u5230\u53f3\u4e0b\u89e3(N,M)\u7684\u7a9d\u4e2d\u53bb\uff0c\u72fc\u738b\u5f00\u59cb\u4f0f\u51fb\u8fd9\u4e9b\u5154 \u5b50.\u5f53\u7136\u4e3a\u4e86\u4fdd\u9669\u8d77\u89c1\uff0c\u5982\u679c\u4e00\u6761\u9053\u8def\u4e0a\u6700\u591a\u901a\u8fc7\u7684\u5154\u5b50\u6570\u4e3aK\uff0c\u72fc\u738b\u9700\u8981\u5b89\u6392\u540c\u6837\u6570\u91cf\u7684K\u53ea\u72fc\uff0c\u624d\u80fd\u5b8c\u5168\u5c01\u9501\u8fd9\u6761\u9053\u8def\uff0c\u4f60\u9700\u8981\u5e2e\u52a9\u72fc\u738b\u5b89\u6392\u4e00\u4e2a\u4f0f\u51fb\u65b9\u6848\uff0c\u4f7f \u5f97\u5728\u5c06\u5154\u5b50\u4e00\u7f51\u6253\u5c3d\u7684\u524d\u63d0\u4e0b\uff0c\u53c2\u4e0e\u7684\u72fc\u7684\u6570\u91cf\u8981\u6700\u5c0f\u3002\u56e0\u4e3a\u72fc\u8fd8\u8981\u53bb\u627e\u559c\u7f8a\u7f8a\u9ebb\u70e6. Input \u7b2c\u4e00\u884c\u4e3aN,M.\u8868\u793a\u7f51\u683c\u7684\u5927\u5c0f\uff0cN,M\u5747\u5c0f\u4e8e\u7b49\u4e8e1000.\u63a5\u4e0b\u6765\u5206\u4e09\u90e8\u5206 \u7b2c\u4e00\u90e8\u5206\u5171N\u884c\uff0c\u6bcf\u884cM-1\u4e2a\u6570\uff0c\u8868\u793a\u6a2a\u5411\u9053\u8def\u7684\u6743\u503c. \u7b2c\u4e8c\u90e8\u5206\u5171N-1\u884c\uff0c\u6bcf\u884cM\u4e2a\u6570\uff0c\u8868\u793a\u7eb5\u5411\u9053\u8def\u7684\u6743\u503c. \u7b2c\u4e09\u90e8\u5206\u5171N-1\u884c\uff0c\u6bcf\u884cM-1\u4e2a\u6570\uff0c\u8868\u793a\u659c\u5411\u9053\u8def\u7684\u6743\u503c. \u8f93\u5165\u6587\u4ef6\u4fdd\u8bc1\u4e0d\u8d85\u8fc710M Output \u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u53c2\u4e0e\u4f0f\u51fb\u7684\u72fc\u7684\u6700\u5c0f\u6570\u91cf. Sample Input 3 45 6 44 3 17 5 35 6 7 88 7 6 55 5 56 6 6 Sample Output 14 Source\u8fd9\u9898\u4e00\u770b\u5c31\u662f\u6700\u5c0f\u5272\u95ee\u9898\uff0c\u4f46\u8303\u56f4\u600e\u4e48\u8fd9\u4e48\u5927\u56e7\u3002\u3002\u3002\u540e\u6765\u770b\u4e86\u5468\u51ac\u795e\u725b\u7684\u8bba\u6587(2008\u5e74\u7684\u90a3\u4e2a)\u624d\u77e5\u9053\u539f\u6765\u5e73\u9762\u56fe\u7684\u6700\u5c0f\u5272\u7b49\u4e8e\u5bf9\u5076\u56fe\u7684\u6700\u77ed\u8def\u56e7\u3002\u3002\u6784\u56fe\u5f88\u9ebb\u70e6\uff0c\u641e\u5f97\u6211\u7d2f\u6b7b\u56e7\u3002\u3002 #include&lt;cstdio&gt;#include&lt;vector&gt;#include&lt;queue&gt;#include&lt;iostream&gt;#define rep(i,n) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/264"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=264"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/264\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=264"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=264"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}