{"id":363,"date":"2010-08-25T13:46:00","date_gmt":"2010-08-25T05:46:00","guid":{"rendered":"http:\/\/localhost\/?p=363"},"modified":"2010-08-25T13:46:00","modified_gmt":"2010-08-25T05:46:00","slug":"ticket_to_ride","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=363","title":{"rendered":"Ticket to Ride"},"content":{"rendered":"\n<p>Time Limit:5000MS&#160; Memory Limit:65536K<br \/>Total Submit:7 Accepted:5 <br \/>Case Time Limit:1000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u7ed9\u4e00\u5f20\u5730\u56fe\uff0c\u5730\u56fe\u4e0a\u6709\u4e00\u4e9b\u57ce\u5e02\uff0c\u57ce\u5e02\u4e4b\u95f4\u53ef\u80fd\u6709\u7ebf\u8def\u8fde\u901a\uff0c\u6211\u4eec\u7528\u4e00\u4e2a\u65e0\u5411\u56fe\u6765\u8868\u793a\u4ee5\u7b80\u5316\u6982\u5ff5\uff0c\u6bcf\u6761\u8fb9\u6709\u4e2a\u6743\u503c\uff0c\u8868\u793a\u9009\u62e9\u8fd9\u6761\u8fb9\u9700\u8981\u82b1\u8d39\u7684\u8d39\u7528\u3002\u7ed9\u5b9a4\u5bf9\u9876 \u70b9(\u53ef\u80fd\u91cd\u590d)\uff0c\u6c42\u4e00\u4e2a\u6743\u503c\u6700\u5c0f\u7684\u8fb9\u96c6\uff0c\u4f7f\u5f97\u4efb\u610f\u4e00\u5bf9\u9876\u70b9\u53ef\u4ee5\u7531\u9009\u51fa\u7684\u8fb9\u96c6\u4e2d\u7684\u8fb9\u76f8\u8fde\u3002 <br \/>\u6309\u7167\u60ef\u4f8b\uff0c\u4e0b\u9762\u7ed9\u51fa\u4e00\u4e2a\u4f8b\u5b50\uff1a <br \/><img decoding=\"async\" src=\"http:\/\/61.187.179.132:8080\/JudgeOnline\/images\/1402.jpg\" \/> <\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c1\u884c2\u4e2a\u6574\u6570\uff0cn\u548cm\uff0c\u5206\u522b\u8868\u793a\u57ce\u5e02\u7684\u4e2a\u6570\u548c\u8fb9\u7684\u4e2a\u6570\u3002 <br \/>\u63a5\u4e0b\u6765n\u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u8868\u793a\u6bcf\u4e2a\u57ce\u5e02\u7684\u540d\u5b57\u3002\u57ce\u5e02\u7684\u540d\u5b57\u4e3a\u4e00\u4e2a\u4e0d\u8d85\u8fc720\u4e2a\u5b57\u7b26\uff0c\u7531\u5c0f\u5199\u5b57\u6bcd\u6784\u6210\u7684\u5b57\u7b26\u4e32\u3002 <br \/>\u518d\u63a5\u4e0b\u6765m\u884c\uff0c\u6bcf\u884c\u7ed9\u51fas1,s2\u548cw\uff0c\u5176\u4e2ds1,s2\u4e3a\u57ce\u5e02\u7684\u540d\u5b57\uff0cw\u4e3a\u4ed6\u4eec\u4e4b\u95f4\u8fb9\u7684\u6743\u503c\u3002 <br \/>\u6700\u540e\uff0c\u7ed9\u51fa4\u884c\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e24\u4e2a\u5b57\u7b26\u4e32\uff0c\u5206\u522b\u4e3a\u8981\u6c42\u7684\u4e00\u5bf9\u57ce\u5e02\u7684\u540d\u5b57\u3002 <\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u4e00\u884c\uff0c\u8f93\u51fa\u6700\u5c0f\u7684\u82b1\u8d39\u3002 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>\u6837\u4f8b\u8f93\u51651\uff1a<br \/>10 15<br \/>stockholm<br \/>amsterdam<br \/>london<br \/>berlin<br \/>copenhagen<br \/>oslo<br \/>helsinki<br \/>dublin<br \/>reykjavik<br \/>brussels<br \/>oslo stockholm 415<br \/>stockholm helsinki 396<br \/>oslo london 1153<br \/>oslo copenhagen 485<br \/>stockholm copenhagen 522<br \/>copenhagen berlin 354<br \/>copenhagen amsterdam 622<br \/>helsinki berlin 1107<br \/>london amsterdam 356<br \/>berlin amsterdam 575<br \/>london dublin 463<br \/>reykjavik dublin 1498<br \/>reykjavik oslo 1748<br \/>london brussels 318<br \/>brussels amsterdam 173<br \/>stockholm amsterdam<br \/>oslo london<br \/>reykjavik dublin<br \/>brussels helsinki<\/p>\n<p>\u6837\u4f8b\u8f93\u51652\uff1a<br \/>2 1<br \/>first<br \/>second<br \/>first second 10<br \/>first first<br \/>first first<br \/>second first<br \/>first first<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>\u6837\u4f8b\u8f93\u51fa1\uff1a<br \/>3907<\/p>\n<p>\u6837\u4f8b\u8f93\u51fa2\uff1a<br \/>10<\/p>\n<p>\u6570\u636e\u8303\u56f4\uff1a<br \/>n&lt;=30,m&lt;=1000,w&lt;=10000\u3002<\/p>\n<p><strong>Source<br \/>\u8fd9\u4e2a\u9898\u76ee\u975e\u5e38\u597d\u554a\u3002\u3002<br \/>\u4ee5\u524dWC\u6709\u9053\u9898\u76ee\u8ddf\u8fd9\u4e2a\u5f88\u7c7b\u4f3c\u3002\u3002<br \/>\u9996\u5148\u7b54\u6848\u80af\u5b9a\u662f\u4e2a\u68ee\u53e6<br \/>\u6240\u4ee5\u72b6\u6001\u53ef\u4ee5\u770b\u6210Dp[at][mask]<br \/>at\u8868\u793a\u5f53\u524d\u6811\u7684\u6839\u5728\u54ea\u91cc\uff0cmask\u8868\u793a\u5230\u8fc7\u7684\u5730\u65b9\uff08\u6700\u591a8\u4f4d\uff09<br \/>\u7136\u540e\u5f00\u59cb\u8f6c\u79fb\uff0c\u8ddf\u90a3\u4e2a\u4e0d\u540c\u7684\u662f\uff0c<br \/>\u5982\u679cmask\u91cc\u9762\u72b6\u6001\u662f\u4e24\u4e24\u914d\u5bf9\u7684\u8bdd\uff0c<br \/>\u90a3\u4e48\u8f6c\u79fb\u7684\u65f6\u5019\u7ecf\u8fc7\u7684\u8fb9\u6743\u53ef\u4ee5\u5ffd\u7565\u3002\u3002<br \/>\u90a3\u4e48\u67092\u79cd\u8f6c\u79fb\u3002\u4e00\u79cd\u662fat-&gt;go\u53e6\u4e00\u4e2a\u5730\u65b9\u3002\u3002<br \/>\u53e6\u4e00\u4e2a\u662f\u628a\u540c\u6837\u5728at\u7684\u4e00\u4e2a\u72b6\u6001\u5408\u5e76\u8fdb\u6765\u3002\u3002<br \/>\u7136\u540e\u778e\u641e\u4e00\u4e0b\u5c31OK\u4e86:<br \/>Code:<br \/><\/strong><\/p>\n<p>#include &lt;algorithm&gt;<br \/>#include &lt;iostream&gt;<br \/>#include &lt;cstdio&gt;<br \/>#include &lt;queue&gt;<br \/>#include &lt;string&gt;<br \/>#include &lt;cstring&gt;<br \/>#include &lt;map&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>const int inf=~0U&gt;&gt;1,maxn=30,maxc=8;<br \/>using namespace std;<br \/>map&lt;string,int&gt; Map;<br \/>vector&lt;int&gt; Mark[maxn];<br \/>int n,m,Ans=inf;<br \/>int E[maxn][maxn];<br \/>struct State<br \/>{<br \/>    int at,mask;<br \/>    State(){}<br \/>    State(int _at,int _mask):<br \/>        at(_at),mask(_mask){}<br \/>    void mark(int go)<br \/>    {<br \/>        rep(i,Mark.size())<br \/>            mask|=1&lt;&lt;(Mark[i]);<br \/>    }<br \/>    bool full()<br \/>    {<br \/>        return mask+1==(1&lt;&lt;8);<br \/>    }<br \/>    bool movefree()<br \/>    {<br \/>        rep(i,4)<br \/>        {<br \/>            int t=(mask&gt;&gt;(i*2))&amp;3;<br \/>            if(t!=0&amp;&amp;t!=3)return false;<br \/>        }<br \/>        return true;<br \/>    }<br \/>    int hash()const{return (at&lt;&lt;8)+mask;}<br \/>};<br \/>queue&lt;State&gt; Q;<br \/>int TDist[maxn&lt;&lt;8];<br \/>bool TinQ[maxn&lt;&lt;8];<br \/>int&amp;Dist(const State&amp;st){return TDist[st.hash()];}<br \/>bool&amp;inQ(const State&amp;st){return TinQ[st.hash()];}<br \/>void spfa()<br \/>{<br \/>    memset(TDist,-1,sizeof TDist);<br \/>    memset(TinQ,0,sizeof TinQ);<br \/>    rep(at,n)<br \/>    {<br \/>        State now(at,0);<br \/>        now.mark(at);<br \/>        Dist(now)=0;inQ(now)=true;<br \/>        Q.push(now);<br \/>    }<br \/>    while(Q.size())<br \/>    {<br \/>        State now=Q.front();Q.pop();<br \/>        int c=Dist(now);inQ(now)=false;<br \/>        if(now.full())<br \/>        {<br \/>            if(c&lt;Ans)Ans=c;<br \/>            continue;<br \/>        }<br \/>        bool free=now.movefree();<br \/>        State next;int w;<br \/>        \/\/let&#8217;s go<br \/>        rep(go,n)<br \/>            if((w=E[now.at])!=inf)<br \/>            {<br \/>                if(free)w=0;<br \/>                int nc=c+w;<br \/>                next.at=go;next.mask=now.mask;<br \/>                next.mark(go);<br \/>                if(Dist(next)==-1||Dist(next)&gt;nc)<br \/>                {<br \/>                    Dist(next)=nc;<br \/>                    if(!inQ(next))<br \/>                        Q.push(next),inQ(next)=true;<br \/>                }<br \/>            }<br \/>        \/\/or we merge somthing<br \/>        rep(j,(1&lt;&lt;8))<br \/>        {<br \/>            State tmp(now.at,j);<br \/>            int tmpc=Dist(tmp);<br \/>            if(tmpc!=-1)<br \/>            {<br \/>                State next(now.at,j|(now.mask));<br \/>                int nc=tmpc+c;<br \/>                if(Dist(next)==-1||Dist(next)&gt;nc)<br \/>                {<br \/>                    Dist(next)=nc;<br \/>                    if(!inQ(next))<br \/>                        Q.push(next),inQ(next)=true;<br \/>                }<br \/>            }<br \/>        }<br \/>    }<br \/>}<br \/>void init()<br \/>{<br \/>    cin&gt;&gt;n&gt;&gt;m;string a,b;int c;<br \/>    rep(i,n)rep(j,n)E[i][j]=inf;<br \/>    rep(i,n)cin&gt;&gt;a,Map[a]=i;<br \/>    rep(i,m)<br \/>    {<br \/>        cin&gt;&gt;a&gt;&gt;b&gt;&gt;c;<br \/>        int s=Map[a],t=Map[b];<br \/>        E[s][t]=E[t][s]=min(E[s][t],c);<br \/>    }<br \/>    memset(Mark,-1,sizeof Mark);<br \/>    rep(i,8)<br \/>    {<br \/>        cin&gt;&gt;a;Mark[Map[a]].push_back(i);<br \/>    }<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    \/\/freopen(&quot;out&quot;,&quot;w&quot;,stdout);<br \/>    init();<br \/>    spfa();<br \/>    cout&lt;&lt;Ans&lt;&lt;endl;<br \/>}<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Time Limit:5000MS&#160; Memory Limit:65536KTotal Submit:7 Accepted:5 Case Time Limit:1000MS Description \u7ed9\u4e00\u5f20\u5730\u56fe\uff0c\u5730\u56fe\u4e0a\u6709\u4e00\u4e9b\u57ce\u5e02\uff0c\u57ce\u5e02\u4e4b\u95f4\u53ef\u80fd\u6709\u7ebf\u8def\u8fde\u901a\uff0c\u6211\u4eec\u7528\u4e00\u4e2a\u65e0\u5411\u56fe\u6765\u8868\u793a\u4ee5\u7b80\u5316\u6982\u5ff5\uff0c\u6bcf\u6761\u8fb9\u6709\u4e2a\u6743\u503c\uff0c\u8868\u793a\u9009\u62e9\u8fd9\u6761\u8fb9\u9700\u8981\u82b1\u8d39\u7684\u8d39\u7528\u3002\u7ed9\u5b9a4\u5bf9\u9876 \u70b9(\u53ef\u80fd\u91cd\u590d)\uff0c\u6c42\u4e00\u4e2a\u6743\u503c\u6700\u5c0f\u7684\u8fb9\u96c6\uff0c\u4f7f\u5f97\u4efb\u610f\u4e00\u5bf9\u9876\u70b9\u53ef\u4ee5\u7531\u9009\u51fa\u7684\u8fb9\u96c6\u4e2d\u7684\u8fb9\u76f8\u8fde\u3002 \u6309\u7167\u60ef\u4f8b\uff0c\u4e0b\u9762\u7ed9\u51fa\u4e00\u4e2a\u4f8b\u5b50\uff1a Input \u7b2c1\u884c2\u4e2a\u6574\u6570\uff0cn\u548cm\uff0c\u5206\u522b\u8868\u793a\u57ce\u5e02\u7684\u4e2a\u6570\u548c\u8fb9\u7684\u4e2a\u6570\u3002 \u63a5\u4e0b\u6765n\u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u8868\u793a\u6bcf\u4e2a\u57ce\u5e02\u7684\u540d\u5b57\u3002\u57ce\u5e02\u7684\u540d\u5b57\u4e3a\u4e00\u4e2a\u4e0d\u8d85\u8fc720\u4e2a\u5b57\u7b26\uff0c\u7531\u5c0f\u5199\u5b57\u6bcd\u6784\u6210\u7684\u5b57\u7b26\u4e32\u3002 \u518d\u63a5\u4e0b\u6765m\u884c\uff0c\u6bcf\u884c\u7ed9\u51fas1,s2\u548cw\uff0c\u5176\u4e2ds1,s2\u4e3a\u57ce\u5e02\u7684\u540d\u5b57\uff0cw\u4e3a\u4ed6\u4eec\u4e4b\u95f4\u8fb9\u7684\u6743\u503c\u3002 \u6700\u540e\uff0c\u7ed9\u51fa4\u884c\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e24\u4e2a\u5b57\u7b26\u4e32\uff0c\u5206\u522b\u4e3a\u8981\u6c42\u7684\u4e00\u5bf9\u57ce\u5e02\u7684\u540d\u5b57\u3002 Output \u4e00\u884c\uff0c\u8f93\u51fa\u6700\u5c0f\u7684\u82b1\u8d39\u3002 Sample Input \u6837\u4f8b\u8f93\u51651\uff1a10 15stockholmamsterdamlondonberlincopenhagenoslohelsinkidublinreykjavikbrusselsoslo stockholm 415stockholm helsinki 396oslo london 1153oslo copenhagen 485stockholm copenhagen 522copenhagen berlin 354copenhagen amsterdam 622helsinki berlin 1107london amsterdam 356berlin amsterdam 575london dublin 463reykjavik dublin 1498reykjavik oslo 1748london brussels 318brussels amsterdam 173stockholm amsterdamoslo [&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\/363"}],"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=363"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/363\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}