{"id":200,"date":"2010-03-30T12:34:00","date_gmt":"2010-03-30T04:34:00","guid":{"rendered":"http:\/\/localhost\/?p=200"},"modified":"2010-03-30T12:34:00","modified_gmt":"2010-03-30T04:34:00","slug":"usaco2009_dec_toll_tolls","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=200","title":{"rendered":"[Usaco2009 Dec]Toll \u8fc7\u8def\u8d39"},"content":{"rendered":"\n

[Usaco2009 Dec]Toll \u8fc7\u8def\u8d39<\/p>\n

Time Limit:10000MS Memory Limit:65536K
Total Submit:14 Accepted:10
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u8ddf\u6240\u6709\u4eba\u4e00\u6837\uff0c\u519c\u592b\u7ea6\u7ff0\u4ee5\u7740\u5b81\u6559\u6211\u8d1f\u5929\u4e0b\u725b\uff0c\u4f11\u53eb\u5929\u4e0b\u725b\u8d1f\u6211\u7684\u4f1f\u5927\u7cbe\u795e\uff0c\u65e5\u65e5\u591c\u591c\u82e6\u601d\u751f
\u8d22\u4e4b\u9053\u3002\u4e3a\u4e86\u53d1\u8d22\uff0c\u4ed6\u8bbe\u7f6e\u4e86\u4e00\u7cfb\u5217\u7684\u89c4\u7ae0\u5236\u5ea6\uff0c\u4f7f\u5f97\u4efb\u4f55\u4e00\u53ea\u5976\u725b\u5728\u519c\u573a\u4e2d\u7684\u9053\u8def\u884c\u8d70\uff0c\u90fd
\u8981\u5411\u519c\u592b\u7ea6\u7ff0\u4e0a\u4ea4\u8fc7\u8def\u8d39\u3002 <\/p>\n

\u519c\u573a\u4e2d\u7531N\uff081 <= N <= 250\uff09\u7247\u8349\u5730\uff08\u6807\u53f7\u4e3a1\u5230N\uff09\uff0c\u5e76\u4e14\u6709M\uff081 <= M <= 10000\uff09\u6761
\u53cc\u5411\u9053\u8def\u8fde\u63a5\u8349\u5730A_j\u548cB_j\uff081 <= A_j <= N; 1 <= B_j <= N\uff09\u3002\u5976\u725b\u4eec\u4ece\u4efb\u610f\u4e00\u7247\u8349
\u5730\u51fa\u53d1\u53ef\u4ee5\u62b5\u8fbe\u4efb\u610f\u4e00\u7247\u7684\u8349\u5730\u3002FJ\u5df2\u7ecf\u5728\u8fde\u63a5A_j\u548cB_j\u7684\u53cc\u5411\u9053\u8def\u4e0a\u8bbe\u7f6e\u4e00\u4e2a\u8fc7\u8def\u8d39L_j
\uff081 <= L_j <= 100,000\uff09\u3002 <\/p>\n

\u53ef\u80fd\u6709\u591a\u6761\u9053\u8def\u8fde\u63a5\u76f8\u540c\u7684\u4e24\u7247\u8349\u5730\uff0c\u4f46\u662f\u4e0d\u5b58\u5728\u4e00\u6761\u9053\u8def\u8fde\u63a5\u4e00\u7247\u8349\u5730\u548c\u8fd9\u7247\u8349\u5730\u672c\u8eab\u3002\u6700
\u503c\u5f97\u5e86\u5e78\u7684\u662f\uff0c\u5976\u725b\u4ece\u4efb\u610f\u4e00\u7bc7\u8349\u5730\u51fa\u53d1\uff0c\u7ecf\u8fc7\u4e00\u7cfb\u5217\u7684\u8def\u5f84\uff0c\u603b\u662f\u53ef\u4ee5\u62b5\u8fbe\u5176\u5b83\u7684\u4efb\u610f\u4e00\u7247
\u8349\u5730\u3002 <\/p>\n

\u9664\u4e86\u8d2a\u5f97\u65e0\u538c\uff0c\u53eb\u517d\u90fd\u4e0d\u77e5\u9053\u8be5\u8bf4\u4ec0\u4e48\u597d\u3002FJ\u7adf\u7136\u5728\u6bcf\u7247\u8349\u5730\u4e0a\u9762\u4e5f\u8bbe\u7f6e\u4e86\u4e00\u4e2a\u8fc7\u8def\u8d39C_i
\uff081 <= C_i <= 100000\uff09\u3002\u4ece\u4e00\u7247\u8349\u5730\u5230\u53e6\u5916\u4e00\u7247\u8349\u5730\u7684\u8d39\u7528\uff0c\u662f\u7ecf\u8fc7\u7684\u6240\u6709\u9053\u8def\u7684\u8fc7\u8def
\u8d39\u4e4b\u548c\uff0c\u52a0\u4e0a\u7ecf\u8fc7\u7684\u6240\u6709\u7684\u8349\u5730\uff08\u5305\u62ec\u8d77\u70b9\u548c\u7ec8\u70b9\uff09\u7684\u8fc7\u8def\u8d39\u7684\u6700\u5927\u503c\u3002 <\/p>\n

\u4efb\u52b3\u4efb\u6028\u7684\u725b\u4eec\u5e0c\u671b\u53bb\u8c03\u67e5\u4e00\u4e0b\u5979\u4eec\u5e94\u8be5\u9009\u62e9\u90a3\u4e00\u6761\u8def\u5f84\u3002\u5979\u4eec\u8981\u4f60\u5199\u4e00\u4e2a\u7a0b\u5e8f\uff0c\u63a5\u53d7K\uff081
<= K <= 10,000\uff09\u4e2a\u95ee\u9898\u5e76\u4e14\u8f93\u51fa\u6bcf\u4e2a\u8be2\u95ee\u5bf9\u5e94\u7684\u6700\u5c0f\u82b1\u8d39\u3002\u7b2ci\u4e2a\u95ee\u9898\u5305\u542b\u4e24\u4e2a\u6570\u5b57s_i
\u548ct_i\uff081 <= s_i <= N; 1 <= t_i <= N; s_i != t_i\uff09\uff0c\u8868\u793a\u8d77\u70b9\u548c\u7ec8\u70b9\u7684\u8349\u5730\u3002 <\/p>\n

\u8003\u8651\u4e0b\u9762\u8fd9\u4e2a\u5305\u542b5\u7247\u8349\u5730\u7684\u6837\u4f8b\u56fe\u50cf:
<\/p>\n

\u4ece\u8349\u57301\u5230\u8349\u57303\u7684\u9053\u8def\u7684“\u8fb9\u8fc7\u8def\u8d39”\u4e3a3\uff0c\u8349\u57302\u7684“\u70b9\u8fc7\u8def\u8d39”\u4e3a5\u3002 <\/p>\n

\u8981\u4ece\u8349\u57301\u8d70\u5230\u8349\u57304\uff0c\u53ef\u4ee5\u4ece\u8349\u57301\u8d70\u5230\u8349\u57303\u518d\u8d70\u5230\u8349\u57305\u6700\u540e\u62b5\u8fbe\u8349\u57304\u3002\u5982\u679c\u8fd9\u4e48\u8d70\u7684\u8bdd\uff0c
\u9700\u8981\u7684“\u8fb9\u8fc7\u8def\u8d39”\u4e3a2+1+1=4\uff0c\u9700\u8981\u7684\u70b9\u8fc7\u8def\u8d39\u4e3a4\uff08\u8349\u57305\u7684\u70b9\u8fc7\u8def\u8d39\u6700\u5927\uff09\uff0c\u6240\u4ee5\u603b\u7684\u82b1
\u8d39\u4e3a4+4=8\u3002 <\/p>\n

\u800c\u4ece\u8349\u57302\u5230\u8349\u57303\u7684\u6700\u4f73\u8def\u5f84\u662f\u4ece\u8349\u57302\u51fa\u53d1\uff0c\u62b5\u8fbe\u8349\u57305\uff0c\u6700\u540e\u5230\u8fbe\u8349\u57303\u3002\u8fd9\u4e48\u8d70\u7684\u8bdd\uff0c\u8fb9
\u8fc7\u8def\u8d39\u4e3a3+1=4\uff0c\u70b9\u8fc7\u8def\u8d39\u4e3a5\uff0c\u603b\u82b1\u8d39\u4e3a4+5=9\u3002 <\/p>\n

<\/p>\n

Input <\/strong><\/p>\n

* \u7b2c1\u884c: \u4e09\u4e2a\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570: N, M\u548cK <\/p>\n

* \u7b2c2\u5230\u7b2cN+1\u884c: \u7b2ci+1\u884c\u5305\u542b\u4e00\u4e2a\u5355\u72ec\u7684\u6574\u6570: C_i <\/p>\n

* \u7b2cN+2\u5230\u7b2cN+M+1\u884c: \u7b2cj+N+1\u884c\u5305\u542b3\u4e2a\u7531\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570: A_j, B_j\u548cL_j <\/p>\n

* \u7b2cN+M+2\u5012\u7b2cN+M+K+1\u884c: \u7b2ci+N+M+1\u884c\u8868\u793a\u7b2ci\u4e2a\u95ee\u9898\uff0c\u5305\u542b\u4e24\u4e2a\u7531\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570s_i
\u548ct_i <\/p>\n

Output <\/strong><\/p>\n

* \u7b2c1\u5230\u7b2cK\u884c: \u7b2ci\u884c\u5305\u542b\u4e00\u4e2a\u5355\u72ec\u7684\u6574\u6570\uff0c\u8868\u793a\u4eces_i\u5230t_i\u7684\u6700\u5c0f\u82b1\u8d39\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Source <\/strong><\/p>\n

Gold<\/p>\n

\u997f\u3002\u3002\u60b2\u5267\u3002\u5f53\u65f6\u7684\u6bd4\u8d5b\u56e0\u4e3a\u8981\u4e2d\u8003\u6ca1\u53c2\u52a0\u56e7\u3002\u3002\u8fd9\u9053\u9898\u76ee\u8fd8\u662f\u633a\u6709\u610f\u601d\u7684\uff0c\u9996\u5148n\u5f88\u5c0f\uff0c\u8be2\u95ee\u5f88\u591a\u53ea\u597d\u9884\u5904\u7406\uff0c\u9884\u5904\u7406\u4e0d\u80fd\u4e0d\u60f3\u5230floyd\uff0c\u4e0d\u8fc7floyd\u5982\u679c\u76f4\u63a5\u6309\u539f\u6765\u7684\u987a\u5e8f\u679a\u4e3ek\u662f\u641e\u4e0d\u51fa\u6765\u7684\u56e7\u3002\u3002\u5b9e\u9645\u4e0a\u53ea\u8981\u6309C\u7684\u987a\u5e8f\u679a\u4e3ek\u5c31\u53ef\u4ee5\u4e86\u56e7\u3002\u3002
Code\uff1a<\/p>\n

#include<iostream>#include<cstdio>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int inf=~0U>>3,maxn=250;int D[maxn][maxn],Ans[maxn][maxn],n,m,q,C[maxn],P[maxn];void Init(){ cin>>n>>m>>q;rep(i,n)scanf("%d",C+i),P[i]=i;int s,t,c; rep(i,n)rep(j,n)D[i][j]=Ans[i][j]=inf; rep(i,n)D[i][i]=0; rep(i,m)scanf("%d %d %d",&s,&t,&c),–s,–t,D[s][t]=D[t][s]=min(D[s][t],c);}bool cmp(int a,int b){return C[a]<C[b];}inline void Renew(int&x,int c){x=min(x,c);}void Work(){ sort(P,P+n,cmp); rep(t,n) { int k=P[t]; rep(i,n)rep(j,n)if(C[i]<=C[k]&&C[j]<=C[k])Renew(Ans[i][j],D[i][k]+D[k][j]+C[k]); rep(i,n)rep(j,n)Renew(D[i][j],D[i][k]+D[k][j]); } int s,t; rep(i,q)scanf("%d %d",&s,&t),–s,–t,printf("%dn",Ans[s][t]);}int main(){ \/\/freopen("in","r",stdin); Init(); Work();}895 7 2253341 2 31 3 22 5 35 3 15 4 12 4 33 4 41 42 3 <\/p>\n","protected":false},"excerpt":{"rendered":"

[Usaco2009 Dec]Toll \u8fc7\u8def\u8d39 Time Limit:10000MS Memory Limit:65536KTotal Submit:14 Accepted:10 Case Time Limit:1000MS Description \u8ddf\u6240\u6709\u4eba\u4e00\u6837\uff0c\u519c\u592b\u7ea6\u7ff0\u4ee5\u7740\u5b81\u6559\u6211\u8d1f\u5929\u4e0b\u725b\uff0c\u4f11\u53eb\u5929\u4e0b\u725b\u8d1f\u6211\u7684\u4f1f\u5927\u7cbe\u795e\uff0c\u65e5\u65e5\u591c\u591c\u82e6\u601d\u751f \u8d22\u4e4b\u9053\u3002\u4e3a\u4e86\u53d1\u8d22\uff0c\u4ed6\u8bbe\u7f6e\u4e86\u4e00\u7cfb\u5217\u7684\u89c4\u7ae0\u5236\u5ea6\uff0c\u4f7f\u5f97\u4efb\u4f55\u4e00\u53ea\u5976\u725b\u5728\u519c\u573a\u4e2d\u7684\u9053\u8def\u884c\u8d70\uff0c\u90fd \u8981\u5411\u519c\u592b\u7ea6\u7ff0\u4e0a\u4ea4\u8fc7\u8def\u8d39\u3002 \u519c\u573a\u4e2d\u7531N\uff081 <= N <= 250\uff09\u7247\u8349\u5730\uff08\u6807\u53f7\u4e3a1\u5230N\uff09\uff0c\u5e76\u4e14\u6709M\uff081 <= M <= 10000\uff09\u6761 \u53cc\u5411\u9053\u8def\u8fde\u63a5\u8349\u5730A_j\u548cB_j\uff081 <= A_j <= N; 1 <= B_j <= N\uff09\u3002\u5976\u725b\u4eec\u4ece\u4efb\u610f\u4e00\u7247\u8349 \u5730\u51fa\u53d1\u53ef\u4ee5\u62b5\u8fbe\u4efb\u610f\u4e00\u7247\u7684\u8349\u5730\u3002FJ\u5df2\u7ecf\u5728\u8fde\u63a5A_j\u548cB_j\u7684\u53cc\u5411\u9053\u8def\u4e0a\u8bbe\u7f6e\u4e00\u4e2a\u8fc7\u8def\u8d39L_j \uff081 <= L_j <= 100,000\uff09\u3002 \u53ef\u80fd\u6709\u591a\u6761\u9053\u8def\u8fde\u63a5\u76f8\u540c\u7684\u4e24\u7247\u8349\u5730\uff0c\u4f46\u662f\u4e0d\u5b58\u5728\u4e00\u6761\u9053\u8def\u8fde\u63a5\u4e00\u7247\u8349\u5730\u548c\u8fd9\u7247\u8349\u5730\u672c\u8eab\u3002\u6700 \u503c\u5f97\u5e86\u5e78\u7684\u662f\uff0c\u5976\u725b\u4ece\u4efb\u610f\u4e00\u7bc7\u8349\u5730\u51fa\u53d1\uff0c\u7ecf\u8fc7\u4e00\u7cfb\u5217\u7684\u8def\u5f84\uff0c\u603b\u662f\u53ef\u4ee5\u62b5\u8fbe\u5176\u5b83\u7684\u4efb\u610f\u4e00\u7247 \u8349\u5730\u3002 \u9664\u4e86\u8d2a\u5f97\u65e0\u538c\uff0c\u53eb\u517d\u90fd\u4e0d\u77e5\u9053\u8be5\u8bf4\u4ec0\u4e48\u597d\u3002FJ\u7adf\u7136\u5728\u6bcf\u7247\u8349\u5730\u4e0a\u9762\u4e5f\u8bbe\u7f6e\u4e86\u4e00\u4e2a\u8fc7\u8def\u8d39C_i \uff081 <= C_i <= 100000\uff09\u3002\u4ece\u4e00\u7247\u8349\u5730\u5230\u53e6\u5916\u4e00\u7247\u8349\u5730\u7684\u8d39\u7528\uff0c\u662f\u7ecf\u8fc7\u7684\u6240\u6709\u9053\u8def\u7684\u8fc7\u8def \u8d39\u4e4b\u548c\uff0c\u52a0\u4e0a\u7ecf\u8fc7\u7684\u6240\u6709\u7684\u8349\u5730\uff08\u5305\u62ec\u8d77\u70b9\u548c\u7ec8\u70b9\uff09\u7684\u8fc7\u8def\u8d39\u7684\u6700\u5927\u503c\u3002 \u4efb\u52b3\u4efb\u6028\u7684\u725b\u4eec\u5e0c\u671b\u53bb\u8c03\u67e5\u4e00\u4e0b\u5979\u4eec\u5e94\u8be5\u9009\u62e9\u90a3\u4e00\u6761\u8def\u5f84\u3002\u5979\u4eec\u8981\u4f60\u5199\u4e00\u4e2a\u7a0b\u5e8f\uff0c\u63a5\u53d7K\uff081 <= K <= […]<\/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\/200"}],"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=200"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/200\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=200"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=200"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=200"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}