{"id":165,"date":"2010-03-20T01:16:00","date_gmt":"2010-03-19T17:16:00","guid":{"rendered":"http:\/\/localhost\/?p=165"},"modified":"2010-03-20T01:16:00","modified_gmt":"2010-03-19T17:16:00","slug":"zjoi2006_logistics_and_transport_trans","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=165","title":{"rendered":"[ZJOI2006]\u7269\u6d41\u8fd0\u8f93trans"},"content":{"rendered":"<p> <a href=\"http:\/\/61.187.179.132:8080\/JudgeOnline\/showproblem?problem_id=1003\" target=\"_blank\">61.187.179.132:8080\/JudgeOnline\/showproblem<\/a><\/p>\n<p>[ZJOI2006]\u7269\u6d41\u8fd0\u8f93trans<\/p>\n<p>Time Limit:10000MS&#160; Memory Limit:165536K<br \/>Total Submit:91 Accepted:33 <br \/>Case Time Limit:1000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u7269\u6d41\u516c\u53f8\u8981\u628a\u4e00\u6279\u8d27\u7269\u4ece\u7801\u5934A\u8fd0\u5230\u7801\u5934B\u3002\u7531\u4e8e\u8d27\u7269\u91cf\u6bd4\u8f83\u5927\uff0c\u9700\u8981n\u5929\u624d\u80fd\u8fd0\u5b8c\u3002\u8d27\u7269\u8fd0\u8f93\u8fc7\u7a0b\u4e2d\u4e00\u822c\u8981\u8f6c\u505c\u597d\u51e0\u4e2a\u7801\u5934\u3002\u7269\u6d41\u516c\u53f8\u901a\u5e38\u4f1a\u8bbe\u8ba1\u4e00\u6761\u56fa\u5b9a\u7684\u8fd0\u8f93 \u8def\u7ebf\uff0c\u4ee5\u4fbf\u5bf9\u6574\u4e2a\u8fd0\u8f93\u8fc7\u7a0b\u5b9e\u65bd\u4e25\u683c\u7684\u7ba1\u7406\u548c\u8ddf\u8e2a\u3002\u7531\u4e8e\u5404\u79cd\u56e0\u7d20\u7684\u5b58\u5728\uff0c\u6709\u7684\u65f6\u5019\u67d0\u4e2a\u7801\u5934\u4f1a\u65e0\u6cd5\u88c5\u5378\u8d27\u7269\u3002\u8fd9\u65f6\u5019\u5c31\u5fc5\u987b\u4fee\u6539\u8fd0\u8f93\u8def\u7ebf\uff0c\u8ba9\u8d27\u7269\u80fd\u591f\u6309\u65f6\u5230\u8fbe\u76ee \u7684\u5730\u3002\u4f46\u662f\u4fee\u6539\u8def\u7ebf\u662f\u4e00\u4ef6\u5341\u5206\u9ebb\u70e6\u7684\u4e8b\u60c5\uff0c\u4f1a\u5e26\u6765\u989d\u5916\u7684\u6210\u672c\u3002\u56e0\u6b64\u7269\u6d41\u516c\u53f8\u5e0c\u671b\u80fd\u591f\u8ba2\u4e00\u4e2an\u5929\u7684\u8fd0\u8f93\u8ba1\u5212\uff0c\u4f7f\u5f97\u603b\u6210\u672c\u5c3d\u53ef\u80fd\u5730\u5c0f\u3002 <\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c\u4e00\u884c\u662f\u56db\u4e2a\u6574\u6570n\uff081&lt;=n&lt;=100\uff09\u3001m\uff081&lt;=m&lt;=20\uff09\u3001K\u548ce\u3002n\u8868\u793a\u8d27\u7269\u8fd0\u8f93\u6240\u9700\u5929\u6570\uff0cm\u8868\u793a\u7801\u5934\u603b\u6570\uff0cK\u8868\u793a \u6bcf\u6b21\u4fee\u6539\u8fd0\u8f93\u8def\u7ebf\u6240\u9700\u6210\u672c\u3002\u63a5\u4e0b\u6765e\u884c\u6bcf\u884c\u662f\u4e00\u6761\u822a\u7ebf\u63cf\u8ff0\uff0c\u5305\u62ec\u4e86\u4e09\u4e2a\u6574\u6570\uff0c\u4f9d\u6b21\u8868\u793a\u822a\u7ebf\u8fde\u63a5\u7684\u4e24\u4e2a\u7801\u5934\u7f16\u53f7\u4ee5\u53ca\u822a\u7ebf\u957f\u5ea6\uff08&gt;0\uff09\u3002\u5176\u4e2d\u7801\u5934A\u7f16\u53f7 \u4e3a1\uff0c\u7801\u5934B\u7f16\u53f7\u4e3am\u3002\u5355\u4f4d\u957f\u5ea6\u7684\u8fd0\u8f93\u8d39\u7528\u4e3a1\u3002\u822a\u7ebf\u662f\u53cc\u5411\u7684\u3002 <br \/>\u518d\u63a5\u4e0b\u6765\u4e00\u884c\u662f\u4e00\u4e2a\u6574\u6570d\uff0c\u540e\u9762\u7684d\u884c\u6bcf\u884c\u662f\u4e09\u4e2a\u6574\u6570P\uff08 1 &lt; P &lt; m\uff09\u3001a\u3001b\uff081 &lt; = a &lt; = b  &lt; =  n\uff09\u3002\u8868\u793a\u7f16\u53f7\u4e3aP\u7684\u7801\u5934\u4ece\u7b2ca\u5929\u5230\u7b2cb\u5929\u65e0\u6cd5\u88c5\u5378\u8d27\u7269\uff08\u542b\u5934\u5c3e\uff09\u3002\u540c\u4e00\u4e2a\u7801\u5934\u6709\u53ef\u80fd\u5728\u591a\u4e2a\u65f6\u95f4\u6bb5\u5185\u4e0d\u53ef\u7528\u3002\u4f46\u4efb\u4f55\u65f6\u95f4\u90fd\u5b58\u5728\u81f3\u5c11\u4e00\u6761\u4ece\u7801\u5934A\u5230\u7801\u5934B\u7684 \u8fd0\u8f93\u8def\u7ebf\u3002 <\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u5305\u62ec\u4e86\u4e00\u4e2a\u6574\u6570\u8868\u793a\u6700\u5c0f\u7684\u603b\u6210\u672c\u3002\u603b\u6210\u672c=n\u5929\u8fd0\u8f93\u8def\u7ebf\u957f\u5ea6\u4e4b\u548c+K*\u6539\u53d8\u8fd0\u8f93\u8def\u7ebf\u7684\u6b21\u6570\u3002 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>5 5 10 8<br \/>1 2 1<br \/>1 3 3<br \/>1 4 2<br \/>2 3 2<br \/>2 4 4<br \/>3 4 1<br \/>3 5 2<br \/>4 5 2<br \/>4<br \/>2 2 3<br \/>3 1 1             <br \/>3 3 3<br \/>4 4 5<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>Sample Output<br \/>32<\/p>\n<p><strong>Hint <\/strong><\/p>\n<p> \u524d\u4e09\u5929\u8d701-4-5\uff0c\u540e\u4e24\u5929\u8d701-3-5\uff0c\u8fd9\u6837\u603b\u6210\u672c\u4e3a(2+2)*3+(3+2)*2+10=32 <\/p>\n<p><strong>Source <\/strong><\/p>\n<p>\u597d\u50cf\u662f\u8001\u9898\u76ee\u4e86\u3002\u3002\u4ee5\u524d\u5728VJ\u4e0a\u770b\u5230\u8fc7\u3002\u4e0d\u8fc7\u6211\u662f\u7b2c\u4e00\u6b21\u505a\u3002\u3002\u8fd8\u6709\u5c31\u662f\u6211\u521a\u521a\u5b9e\u5728\u592a\u65e0\u804a\u4e86\u3002\u3002\u628a\u81ea\u5df1\u4ee5\u524d\u5728PKU\u4e0a\u8fc7\u7684USACO\u6708\u8d5b\u9898\u76ee\u4ea4\u9898\u5e93\u4e86\u3002\u3002\u7ed3\u679c\u5237\u4e86\u4e0d\u5c11Rank\u3002\u3002\u5176\u5b9e\u90fd\u662fUSACO\u7684\u6c34\u9898\u56e7\u3002\u3002PKU\u5c45\u7136\u6709\u4ee3\u7801\u6253\u5305\u7684\u529f\u80fd\u7684\uff0c\u771f\u662f\u592a\u5f3a\u4e86\u4e86Orz\u3002\u3002<br \/>\u8fd9\u9053\u9898\u76ee\u7684\u8bdd\u8bbeDp(i)\u8868\u793a1\u5230i\u5929\u6700\u5c0f\u8d39\u7528\uff0c\u90a3\u4e48Dp(i)=Min(Dp(j)+Cost(j+1,i)*(i-j)+k)..Cost(l,r)\u8868\u793al\u5230r\u671f\u95f4\u90fd\u53ef\u7528\u7684\u6700\u77ed\u8def\u7ebf\u957f\u5ea6\u3002\u3002\u6bcf\u6b21\u90fdspfa\u4e00\u6b21\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u53cd\u6b63\u6570\u636e\u8fd9\u4e48\u5c0f\u60f3\u600e\u4e48\u505a\u90fd\u53ef\u4ee5\u56e7\u3002\u3002<br \/>\u6700\u540e\u518d-\u4e2ak\u5c31OK\u4e86\u3002\u3002<br \/>Code\uff1a<br \/>#include&lt;iostream&gt;<br \/>#include&lt;cstdio&gt;<br \/>#include&lt;algorithm&gt;<br \/>#include&lt;cmath&gt;<br \/>#include&lt;cstdlib&gt;<br \/>#include&lt;cstring&gt;<br \/>#include&lt;string&gt;<br \/>#include&lt;vector&gt;<br \/>#include&lt;set&gt;<br \/>#include&lt;queue&gt;<br \/>#include&lt;map&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>#define For(i,a,b) for(int i=a;i&lt;=b;i++)<br \/>#define all(x) x.begin(),x.end()<br \/>#define pb push_back<br \/>using namespace std;<br \/>const int inf=~0U&gt;&gt;2,maxT=100+1,maxn=20,maxm=1000;<br \/>int T,n,k,m;<br \/>struct Edge<br \/>{<br \/>    int t,c;<br \/>    Edge*next;<br \/>    Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}<br \/>}*E[maxn]={0};<br \/>struct Vertex<br \/>{<br \/>    int D[maxT];<br \/>    Vertex(){memset(D,0,sizeof(D));}<br \/>    void Ins(int l,int r)<br \/>    {<br \/>        For(i,l,r) D[i]=1;<br \/>    }<br \/>    void Set()<br \/>    {<br \/>        For(i,1,T) D[i]+=D[i-1];<br \/>    }<br \/>    bool ok(int l,int r)<br \/>    {<br \/>        return D[r]==D[l-1];<br \/>    }<br \/>}V[maxn];<br \/>void InsEdge(int s,int t,int c)<br \/>{<br \/>    E[s]=new Edge(t,c,E[s]);<br \/>    E[t]=new Edge(s,c,E[t]);<br \/>}<br \/>void Init()<br \/>{<br \/>    cin&gt;&gt;T&gt;&gt;n&gt;&gt;k&gt;&gt;m;int s,t,c;<br \/>    while(m&#8211;)<br \/>    {<br \/>        scanf(&quot;%d %d %d&quot;,&amp;s,&amp;t,&amp;c);<br \/>        InsEdge(s-1,t-1,c);<br \/>    }<br \/>    int p,a,l,r;cin&gt;&gt;p;<br \/>    while(p&#8211;)<br \/>    {<br \/>        scanf(&quot;%d %d %d&quot;,&amp;a,&amp;l,&amp;r);<br \/>        V[a-1].Ins(l,r);<br \/>    }<br \/>    rep(i,n)V[i].Set();<br \/>}<br \/>int Cost(int l,int r)<br \/>{<br \/>    static int dist[maxn];<br \/>    static bool inq[maxn];<br \/>    rep(i,n) dist[i]=inf,inq[i]=false;<br \/>    queue&lt;int&gt; Q;<br \/>    Q.push(0);inq[0]=true;dist[0]=0;<br \/>    while(Q.size())<br \/>    {<br \/>        int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];<br \/>        for(Edge*e=E[t];e;e=e-&gt;next)<br \/>        {<br \/>            int ncost=cost+e-&gt;c,v=e-&gt;t;<br \/>            if(!V[v].ok(l,r))continue;<br \/>            if(dist[v]&gt;ncost)<br \/>            {<br \/>                dist[v]=ncost;<br \/>                if(!inq[v]) Q.push(v),inq[v]=true;<br \/>            }<br \/>        }<br \/>    }<br \/>    return dist[n-1];<br \/>}<br \/>int dp[maxT];<br \/>void Work()<br \/>{<br \/>    dp[0]=0;<br \/>    For(i,1,T)<br \/>    {<br \/>        dp[i]=inf;<br \/>        for(int j=i-1;j&gt;=0;&#8211;j)<br \/>        {<br \/>            int c=Cost(j+1,i);<br \/>            if(c==inf)break;<br \/>            dp[i]=min(dp[i],dp[j]+c*(i-j)+k);<br \/>        }<br \/>    }<br \/>    cout&lt;&lt;dp[T]-k&lt;&lt;endl;<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    Init();<br \/>    Work();<br \/>} <\/p>\n","protected":false},"excerpt":{"rendered":"<p>61.187.179.132:8080\/JudgeOnline\/showproblem [ZJOI2006]\u7269\u6d41\u8fd0\u8f93trans Time Limit:10000MS&#160; Memory Limit:165536KTotal Submit:91 Accepted:33 Case Time Limit:1000MS Description \u7269\u6d41\u516c\u53f8\u8981\u628a\u4e00\u6279\u8d27\u7269\u4ece\u7801\u5934A\u8fd0\u5230\u7801\u5934B\u3002\u7531\u4e8e\u8d27\u7269\u91cf\u6bd4\u8f83\u5927\uff0c\u9700\u8981n\u5929\u624d\u80fd\u8fd0\u5b8c\u3002\u8d27\u7269\u8fd0\u8f93\u8fc7\u7a0b\u4e2d\u4e00\u822c\u8981\u8f6c\u505c\u597d\u51e0\u4e2a\u7801\u5934\u3002\u7269\u6d41\u516c\u53f8\u901a\u5e38\u4f1a\u8bbe\u8ba1\u4e00\u6761\u56fa\u5b9a\u7684\u8fd0\u8f93 \u8def\u7ebf\uff0c\u4ee5\u4fbf\u5bf9\u6574\u4e2a\u8fd0\u8f93\u8fc7\u7a0b\u5b9e\u65bd\u4e25\u683c\u7684\u7ba1\u7406\u548c\u8ddf\u8e2a\u3002\u7531\u4e8e\u5404\u79cd\u56e0\u7d20\u7684\u5b58\u5728\uff0c\u6709\u7684\u65f6\u5019\u67d0\u4e2a\u7801\u5934\u4f1a\u65e0\u6cd5\u88c5\u5378\u8d27\u7269\u3002\u8fd9\u65f6\u5019\u5c31\u5fc5\u987b\u4fee\u6539\u8fd0\u8f93\u8def\u7ebf\uff0c\u8ba9\u8d27\u7269\u80fd\u591f\u6309\u65f6\u5230\u8fbe\u76ee \u7684\u5730\u3002\u4f46\u662f\u4fee\u6539\u8def\u7ebf\u662f\u4e00\u4ef6\u5341\u5206\u9ebb\u70e6\u7684\u4e8b\u60c5\uff0c\u4f1a\u5e26\u6765\u989d\u5916\u7684\u6210\u672c\u3002\u56e0\u6b64\u7269\u6d41\u516c\u53f8\u5e0c\u671b\u80fd\u591f\u8ba2\u4e00\u4e2an\u5929\u7684\u8fd0\u8f93\u8ba1\u5212\uff0c\u4f7f\u5f97\u603b\u6210\u672c\u5c3d\u53ef\u80fd\u5730\u5c0f\u3002 Input \u7b2c\u4e00\u884c\u662f\u56db\u4e2a\u6574\u6570n\uff081&lt;=n&lt;=100\uff09\u3001m\uff081&lt;=m&lt;=20\uff09\u3001K\u548ce\u3002n\u8868\u793a\u8d27\u7269\u8fd0\u8f93\u6240\u9700\u5929\u6570\uff0cm\u8868\u793a\u7801\u5934\u603b\u6570\uff0cK\u8868\u793a \u6bcf\u6b21\u4fee\u6539\u8fd0\u8f93\u8def\u7ebf\u6240\u9700\u6210\u672c\u3002\u63a5\u4e0b\u6765e\u884c\u6bcf\u884c\u662f\u4e00\u6761\u822a\u7ebf\u63cf\u8ff0\uff0c\u5305\u62ec\u4e86\u4e09\u4e2a\u6574\u6570\uff0c\u4f9d\u6b21\u8868\u793a\u822a\u7ebf\u8fde\u63a5\u7684\u4e24\u4e2a\u7801\u5934\u7f16\u53f7\u4ee5\u53ca\u822a\u7ebf\u957f\u5ea6\uff08&gt;0\uff09\u3002\u5176\u4e2d\u7801\u5934A\u7f16\u53f7 \u4e3a1\uff0c\u7801\u5934B\u7f16\u53f7\u4e3am\u3002\u5355\u4f4d\u957f\u5ea6\u7684\u8fd0\u8f93\u8d39\u7528\u4e3a1\u3002\u822a\u7ebf\u662f\u53cc\u5411\u7684\u3002 \u518d\u63a5\u4e0b\u6765\u4e00\u884c\u662f\u4e00\u4e2a\u6574\u6570d\uff0c\u540e\u9762\u7684d\u884c\u6bcf\u884c\u662f\u4e09\u4e2a\u6574\u6570P\uff08 1 &lt; P &lt; m\uff09\u3001a\u3001b\uff081 &lt; = a &lt; = b &lt; = n\uff09\u3002\u8868\u793a\u7f16\u53f7\u4e3aP\u7684\u7801\u5934\u4ece\u7b2ca\u5929\u5230\u7b2cb\u5929\u65e0\u6cd5\u88c5\u5378\u8d27\u7269\uff08\u542b\u5934\u5c3e\uff09\u3002\u540c\u4e00\u4e2a\u7801\u5934\u6709\u53ef\u80fd\u5728\u591a\u4e2a\u65f6\u95f4\u6bb5\u5185\u4e0d\u53ef\u7528\u3002\u4f46\u4efb\u4f55\u65f6\u95f4\u90fd\u5b58\u5728\u81f3\u5c11\u4e00\u6761\u4ece\u7801\u5934A\u5230\u7801\u5934B\u7684 \u8fd0\u8f93\u8def\u7ebf\u3002 Output \u5305\u62ec\u4e86\u4e00\u4e2a\u6574\u6570\u8868\u793a\u6700\u5c0f\u7684\u603b\u6210\u672c\u3002\u603b\u6210\u672c=n\u5929\u8fd0\u8f93\u8def\u7ebf\u957f\u5ea6\u4e4b\u548c+K*\u6539\u53d8\u8fd0\u8f93\u8def\u7ebf\u7684\u6b21\u6570\u3002 Sample Input 5 5 10 81 2 11 3 31 4 22 3 22 4 43 4 13 [&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\/165"}],"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=165"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/165\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=165"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=165"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}