{"id":252,"date":"2010-05-15T20:34:00","date_gmt":"2010-05-15T12:34:00","guid":{"rendered":"http:\/\/localhost\/?p=252"},"modified":"2010-05-15T20:34:00","modified_gmt":"2010-05-15T12:34:00","slug":"sdoi2009_elaxia_route","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=252","title":{"rendered":"[Sdoi2009]Elaxia\u7684\u8def\u7ebf"},"content":{"rendered":"\n<p>[Sdoi2009]Elaxia\u7684\u8def\u7ebf<\/p>\n<p>Time Limit:4000MS&#160; Memory Limit:65536K<br \/>Total Submit:3 Accepted:2 <br \/>Case Time Limit:1000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u6700\u8fd1\uff0cElaxia\u548cw**\u7684\u5173\u7cfb\u7279\u522b\u597d\uff0c\u4ed6\u4eec\u5f88\u60f3\u6574\u5929\u5728\u4e00\u8d77\uff0c\u4f46\u662f\u5927\u5b66\u7684\u5b66\u4e60\u592a\u7d27\u5f20\u4e86\uff0c\u4ed6\u4eec <br \/>\u5fc5\u987b\u5408\u7406\u5730\u5b89\u6392\u4e24\u4e2a\u4eba\u5728\u4e00\u8d77\u7684\u65f6\u95f4\u3002Elaxia\u548cw**\u6bcf\u5929\u90fd\u8981\u5954\u6ce2\u4e8e\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u4e4b\u95f4\uff0c\u4ed6\u4eec <br \/>\u5e0c\u671b\u5728\u8282\u7ea6\u65f6\u95f4\u7684\u524d\u63d0\u4e0b\uff0c\u4e00\u8d77\u8d70\u7684\u65f6\u95f4\u5c3d\u53ef\u80fd\u7684\u957f\u3002 <br \/>\u73b0\u5728\u5df2\u77e5\u7684\u662fElaxia\u548cw**\u6240\u5728\u7684\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u7684\u7f16\u53f7\u4ee5\u53ca\u5b66\u6821\u7684\u5730\u56fe\uff1a\u5730\u56fe\u4e0a\u6709N\u4e2a\u8def <br \/>\u53e3\uff0cM\u6761\u8def\uff0c\u7ecf\u8fc7\u6bcf\u6761\u8def\u90fd\u9700\u8981\u4e00\u5b9a\u7684\u65f6\u95f4\u3002 <br \/>\u5177\u4f53\u5730\u8bf4\uff0c\u5c31\u662f\u8981\u6c42\u65e0\u5411\u56fe\u4e2d\uff0c\u4e24\u5bf9\u70b9\u95f4\u6700\u77ed\u8def\u7684\u6700\u957f\u516c\u5171\u8def\u5f84\u3002<\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c\u4e00\u884c\uff1a\u4e24\u4e2a\u6574\u6570N\u548cM\uff08\u542b\u4e49\u5982\u9898\u76ee\u63cf\u8ff0\uff09\u3002 <br \/>\u7b2c\u4e8c\u884c\uff1a\u56db\u4e2a\u6574\u6570x1\u3001y1\u3001x2\u3001y2\uff081 \u2264 x1 \u2264 N\uff0c1 \u2264 y1 \u2264 N\uff0c1 \u2264 x2 \u2264 N\uff0c1 \u2264 <br \/>\u2264 N\uff09\uff0c\u5206\u522b\u8868\u793aElaxia\u7684\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u53caw**\u7684\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u7684\u6807\u53f7\uff08\u4e24\u5bf9\u70b9\u5206\u522b <br \/>x1,y1\u548cx2,y2\uff09\u3002 <br \/>\u63a5\u4e0b\u6765M\u884c\uff1a\u6bcf\u884c\u4e09\u4e2a\u6574\u6570\uff0cu\u3001v\u3001l\uff081 \u2264 u \u2264 N\uff0c1 \u2264 v \u2264 N\uff0c1 \u2264 l \u2264 10000\uff09\uff0c\u8868 <br \/>u\u548cv\u4e4b\u95f4\u6709\u4e00\u6761\u8def\uff0c\u7ecf\u8fc7\u8fd9\u6761\u8def\u6240\u9700\u8981\u7684\u65f6\u95f4\u4e3al\u3002 <br \/>\u51fa\u51fa\u51fa\u683c\u683c\u683c\u5f0f\u5f0f\u5f0f\uff1a\uff1a\uff1a <br \/>\u4e00\u884c\uff0c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6bcf\u5929\u4e24\u4eba\u5728\u4e00\u8d77\u7684\u65f6\u95f4\uff08\u5373\u6700\u957f\u516c\u5171\u8def\u5f84\u7684\u957f\u5ea6\uff09\u3002<\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u4e00\u884c\uff0c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6bcf\u5929\u4e24\u4eba\u5728\u4e00\u8d77\u7684\u65f6\u95f4\uff08\u5373\u6700\u957f\u516c\u5171\u8def\u5f84\u7684\u957f\u5ea6\uff09<\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>9 10<br \/>1 6 7 8<br \/>1 2 1<br \/>2 5 2<br \/>2 3 3<br \/>3 4 2<br \/>3 9 5<br \/>4 5 3<br \/>4 6 4<br \/>4 7 2<br \/>5 8 1<br \/>7 9 1<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>3<\/p>\n<p><strong>Hint <\/strong><\/p>\n<p> \u5bf9\u4e8e30%\u7684\u6570\u636e\uff0cN \u2264 100\uff1b <br \/>\u5bf9\u4e8e60%\u7684\u6570\u636e\uff0cN \u2264 1000\uff1b <br \/>\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0cN \u2264 1500\uff0c\u8f93\u5165\u6570\u636e\u4fdd\u8bc1\u6ca1\u6709\u91cd\u8fb9\u548c\u81ea\u73af\u3002<\/p>\n<p><strong>Source <\/strong><\/p>\n<p> Day2<br \/>\u989d\u3002\u3002\u770b\u4e0a\u53bb\u5f88\u5413\u4eba\uff0c\u5b9e\u9645\u4e0a\u8fd8\u662f\u86ee\u6c34\u7684\u3002\u3002<br \/>\u9996\u5148\u53ef\u4ee5\u6ce8\u610f\u5230\u516c\u5171\u7684\u8def\u5f84\u5fc5\u7136\u662f\u4e00\u6bb5\u3002\u3002\u7136\u540e\u627e\u51fa\u6240\u6709\u53ef\u4ee5\u540c\u65f6\u51fa\u73b0\u5728\u4e24\u4e2a\u6700\u77ed\u8def\u7684\u8fb9\uff0c\u7528Dp\u6c42\u51fa\u6700\u957f\u7684\u94fe\u5c31OK\u4e86\u3002\u3002\u3002<br \/>Code\uff1a<\/p>\n<p>#include &lt;cstdio&gt;<br \/>#include &lt;cstring&gt;<br \/>#include &lt;algorithm&gt;<br \/>#include &lt;iostream&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>const int inf=~0U&gt;&gt;1,maxn=1500;<br \/>using namespace std;<br \/>int n,m,S[2],T[2];<br \/>struct Edge<br \/>{<br \/>    int t,c;Edge*next;<br \/>    Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}<br \/>}*E[maxn]={};<br \/>void AddEdge(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 \/>int DistS[2][maxn],DistT[2][maxn];<br \/>struct Queue<br \/>{<br \/>    int Q[maxn],h,t;bool inQ[maxn];<br \/>    Queue(){h=t=0;memset(inQ,0,sizeof(inQ));}<br \/>    void inc(int&amp;i){if(++i==maxn)i=0;}<br \/>    void put(int x)<br \/>    {<br \/>        if(inQ[x])return;inQ[x]=true;<br \/>        Q[t]=x;inc(t);<br \/>    }<br \/>    int get()<br \/>    {<br \/>        int tmp=Q[h];inc(h);inQ[tmp]=false;<br \/>        return tmp;<br \/>    }<br \/>    bool empty(){return h==t;}<br \/>};<br \/>void Spfa(int vs,int Dist[maxn])<br \/>{<br \/>    static Queue Q;<br \/>    rep(i,n)Dist[i]=inf;Dist[vs]=0;Q.put(vs);<br \/>    while(!Q.empty())<br \/>    {<br \/>        int t=Q.get(),c=Dist[t];<br \/>        for(Edge*e=E[t];e;e=e-&gt;next)<br \/>            if(c+e-&gt;c&lt;Dist[e-&gt;t])<br \/>                Dist[e-&gt;t]=c+e-&gt;c,Q.put(e-&gt;t);<br \/>    }<br \/>}<br \/>int D[2];<br \/>bool inPath(int v)<br \/>{<br \/>    rep(i,2)if(DistS[i][v]+DistT[i][v]!=D[i])return false;<br \/>    return true;<br \/>}<br \/>bool inPath(int s,Edge*e)<br \/>{<br \/>    rep(i,2)<br \/>    {<br \/>        int Dist=min(DistS[i][s]+DistT[i][e-&gt;t],DistS[i][e-&gt;t]+DistT[i][s])+e-&gt;c;<br \/>        if(Dist!=D[i])return false;<br \/>    }<br \/>    return true;<br \/>}<br \/>bool In[maxn]={};<br \/>int A[maxn],v=0,Dp[maxn]={};<br \/>bool cmp(int i,int j)<br \/>{<br \/>    return DistS[0][i]&lt;DistS[0][j];<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    scanf(&quot;%d%d%d%d%d%d&quot;,&amp;n,&amp;m,S+0,T+0,S+1,T+1);int s,t,c;<br \/>    rep(i,2)S[i]&#8211;,T[i]&#8211;;<br \/>    while(m&#8211;)scanf(&quot;%d%d%d&quot;,&amp;s,&amp;t,&amp;c),&#8211;s,&#8211;t,AddEdge(s,t,c);<br \/>    rep(i,2)Spfa(S[i],DistS[i]),Spfa(T[i],DistT[i]);<br \/>    rep(i,2)D[i]=DistS[i][T[i]];<br \/>    rep(i,n)In[i]=inPath(i),In[i]?A[v++]=i:0;<br \/>    sort(A,A+v,cmp);<br \/>    int ans=0;<br \/>    rep(i,v)<br \/>    {<br \/>        int t=A[i];ans&gt;?=Dp[t];<br \/>        for(Edge*e=E[t];e;e=e-&gt;next)if(In[e-&gt;t]&amp;&amp;inPath(t,e))<br \/>            Dp[e-&gt;t]&gt;?=Dp[t]+e-&gt;c;<br \/>    }<br \/>    cout&lt;&lt;ans&lt;&lt;endl;<br \/>}<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[Sdoi2009]Elaxia\u7684\u8def\u7ebf Time Limit:4000MS&#160; Memory Limit:65536KTotal Submit:3 Accepted:2 Case Time Limit:1000MS Description \u6700\u8fd1\uff0cElaxia\u548cw**\u7684\u5173\u7cfb\u7279\u522b\u597d\uff0c\u4ed6\u4eec\u5f88\u60f3\u6574\u5929\u5728\u4e00\u8d77\uff0c\u4f46\u662f\u5927\u5b66\u7684\u5b66\u4e60\u592a\u7d27\u5f20\u4e86\uff0c\u4ed6\u4eec \u5fc5\u987b\u5408\u7406\u5730\u5b89\u6392\u4e24\u4e2a\u4eba\u5728\u4e00\u8d77\u7684\u65f6\u95f4\u3002Elaxia\u548cw**\u6bcf\u5929\u90fd\u8981\u5954\u6ce2\u4e8e\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u4e4b\u95f4\uff0c\u4ed6\u4eec \u5e0c\u671b\u5728\u8282\u7ea6\u65f6\u95f4\u7684\u524d\u63d0\u4e0b\uff0c\u4e00\u8d77\u8d70\u7684\u65f6\u95f4\u5c3d\u53ef\u80fd\u7684\u957f\u3002 \u73b0\u5728\u5df2\u77e5\u7684\u662fElaxia\u548cw**\u6240\u5728\u7684\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u7684\u7f16\u53f7\u4ee5\u53ca\u5b66\u6821\u7684\u5730\u56fe\uff1a\u5730\u56fe\u4e0a\u6709N\u4e2a\u8def \u53e3\uff0cM\u6761\u8def\uff0c\u7ecf\u8fc7\u6bcf\u6761\u8def\u90fd\u9700\u8981\u4e00\u5b9a\u7684\u65f6\u95f4\u3002 \u5177\u4f53\u5730\u8bf4\uff0c\u5c31\u662f\u8981\u6c42\u65e0\u5411\u56fe\u4e2d\uff0c\u4e24\u5bf9\u70b9\u95f4\u6700\u77ed\u8def\u7684\u6700\u957f\u516c\u5171\u8def\u5f84\u3002 Input \u7b2c\u4e00\u884c\uff1a\u4e24\u4e2a\u6574\u6570N\u548cM\uff08\u542b\u4e49\u5982\u9898\u76ee\u63cf\u8ff0\uff09\u3002 \u7b2c\u4e8c\u884c\uff1a\u56db\u4e2a\u6574\u6570x1\u3001y1\u3001x2\u3001y2\uff081 \u2264 x1 \u2264 N\uff0c1 \u2264 y1 \u2264 N\uff0c1 \u2264 x2 \u2264 N\uff0c1 \u2264 \u2264 N\uff09\uff0c\u5206\u522b\u8868\u793aElaxia\u7684\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u53caw**\u7684\u5bbf\u820d\u548c\u5b9e\u9a8c\u5ba4\u7684\u6807\u53f7\uff08\u4e24\u5bf9\u70b9\u5206\u522b x1,y1\u548cx2,y2\uff09\u3002 \u63a5\u4e0b\u6765M\u884c\uff1a\u6bcf\u884c\u4e09\u4e2a\u6574\u6570\uff0cu\u3001v\u3001l\uff081 \u2264 u \u2264 N\uff0c1 \u2264 v \u2264 N\uff0c1 \u2264 l \u2264 10000\uff09\uff0c\u8868 u\u548cv\u4e4b\u95f4\u6709\u4e00\u6761\u8def\uff0c\u7ecf\u8fc7\u8fd9\u6761\u8def\u6240\u9700\u8981\u7684\u65f6\u95f4\u4e3al\u3002 \u51fa\u51fa\u51fa\u683c\u683c\u683c\u5f0f\u5f0f\u5f0f\uff1a\uff1a\uff1a \u4e00\u884c\uff0c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6bcf\u5929\u4e24\u4eba\u5728\u4e00\u8d77\u7684\u65f6\u95f4\uff08\u5373\u6700\u957f\u516c\u5171\u8def\u5f84\u7684\u957f\u5ea6\uff09\u3002 Output \u4e00\u884c\uff0c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6bcf\u5929\u4e24\u4eba\u5728\u4e00\u8d77\u7684\u65f6\u95f4\uff08\u5373\u6700\u957f\u516c\u5171\u8def\u5f84\u7684\u957f\u5ea6\uff09 Sample [&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\/252"}],"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=252"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/252\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=252"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=252"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=252"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}