{"id":40,"date":"2009-11-25T19:28:00","date_gmt":"2009-11-25T11:28:00","guid":{"rendered":"http:\/\/localhost\/?p=40"},"modified":"2023-01-30T19:02:08","modified_gmt":"2023-01-30T19:02:08","slug":"spoj_1027","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=40","title":{"rendered":"SPOJ 1027"},"content":{"rendered":"<p><a herf=\"https:\/\/www.spoj.pl\/problems\/FPOLICE\/\">https:\/\/www.spoj.pl\/problems\/FPOLICE\/<\/a><br \/>\n<br \/>\u5206\u5c42\u56fe\u6700\u77ed\u8def\u3002\u3002spfa\u3002\u3002\u3002<br \/>\u600e\u4e48\u53ef\u80fd\u8fd9\u4e48\u5feb0.02s\uff1f\u6000\u7591\u6570\u636e\u592a\u6c34\u4e86\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include&lt;iostream&gt;\r\n#include&lt;queue&gt;\r\n#include&lt;vector&gt;\r\n#include&lt;stdio.h&gt;\r\n#define REP(i,n) for(int i=0;i&lt;n;i++)\r\nusing namespace std;\r\nconst int maxn=100,maxt=250+10,inf=~0U&gt;&gt;1;\r\nint Time[maxn][maxn],Risk[maxn][maxn];\r\nint dist[maxn][maxt];\r\nbool inQ[maxn][maxt];\r\nint N,T;\r\nstruct node\r\n{\r\n    int n,t;\r\n    node(int n,int t):n(n),t(t) {}\r\n};\r\nqueue&lt;node&gt; Q;\r\nvoid solve()\r\n{\r\n    cin&gt;&gt;N&gt;&gt;T;\r\n    REP(i,N) REP(j,N) scanf(&quot;%d&quot;,&amp;Time[i][j]);\r\n    REP(i,N) REP(j,N) scanf(&quot;%d&quot;,&amp;Risk[i][j]);\r\n    REP(i,N) REP(j,T+1) dist[i][j]=inf,inQ[i][j]=false;\r\n    dist[0][0]=0;\r\n    Q.push(node(0,0));\r\n    inQ[0][0]=true;\r\n    while(Q.size())\r\n    {\r\n        node cur=Q.front();\r\n        Q.pop();\r\n        inQ[cur.n][cur.t]=false;\r\n        int cost=dist[cur.n][cur.t],get,nt;\r\n        for(int i=0; i&lt;N; i++) if(i!=cur.n)\r\n            {\r\n                if((nt=Time[cur.n][i]+cur.t)&gt;T) continue;\r\n                get=cost+Risk[cur.n][i];\r\n                if(get&lt;dist[i][nt])\r\n                {\r\n                    dist[i][nt]=get;\r\n                    if(!inQ[i][nt])\r\n                    {\r\n                        Q.push(node(i,nt));\r\n                        inQ[i][nt]=true;\r\n                    }\r\n                }\r\n            }\r\n    }\r\n    int Min=inf,x=-1;\r\n    REP(i,T+1)\r\n    if(dist[N-1][i]&lt;Min)\r\n        Min=dist[N-1][i],x=i;\r\n    if(x==-1)\r\n    {\r\n        cout&lt;&lt;-1&lt;&lt;endl;\r\n        return;\r\n    }\r\n    cout&lt;&lt;Min&lt;&lt;&quot; &quot;&lt;&lt;x&lt;&lt;endl;\r\n}\r\nint main()\r\n{\r\n    int t;\r\n    cin&gt;&gt;t;\r\n    while(t\u2013) solve();\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.spoj.pl\/problems\/FPOLICE\/ \u5206\u5c42\u56fe\u6700\u77ed\u8def\u3002\u3002spfa\u3002\u3002\u3002\u600e\u4e48\u53ef\u80fd\u8fd9\u4e48\u5feb0.02s\uff1f\u6000\u7591\u6570\u636e\u592a\u6c34\u4e86\u3002\u3002\u3002<\/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\/40"}],"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=40"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/40\/revisions"}],"predecessor-version":[{"id":771,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/40\/revisions\/771"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}