{"id":856,"date":"2019-04-07T00:03:17","date_gmt":"2019-04-06T16:03:17","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=856"},"modified":"2019-04-12T16:05:27","modified_gmt":"2019-04-12T08:05:27","slug":"lp2387-noi2014-%e9%ad%94%e6%b3%95%e6%a3%ae%e6%9e%97","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/04\/07\/lp2387-noi2014-%e9%ad%94%e6%b3%95%e6%a3%ae%e6%9e%97\/","title":{"rendered":"lp2387 NOI2014 \u9b54\u6cd5\u68ee\u6797"},"content":{"rendered":"\n

\u8fd9\u4e00\u9898\u636e\u8bf4\u662fLCT\u7ef4\u62a4\u8fb9\u6743\u7684\u9898\u76ee\u3002\u4f46\u662f\u6211\u4eec\u89c2\u5bdf\u4e00\u4e0b\u611f\u89c9\u53ef\u4ee5\u7528\u52a8\u6001\u52a0\u8fb9SPFA\u6765\u8dd1\u8fd9\u9053\u9898\u3002\n\u5177\u4f53\u6765\u8bf4\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u6761\u52a0\u8fdb\u6765\u7684\u8fb9\uff0c\u6211\u4eec\u77e5\u9053\uff0c\u5e76\u4e0d\u662f\u6574\u5f20\u56fe\u90fd\u56e0\u4e3a\u8fd9\u6761\u8fb9\u800c\u6539\u53d8\u3002\u8fd9\u6761\u8fb9\u4f1a\u6539\u53d8\u7684\u6709\u4e14\u4ec5\u6709\u56fe\u7684\u4e00\u90e8\u5206\u3002\n\u56e0\u6b64\uff0c\u6211\u4eec\u4e0d\u59a8\u5c06\u6240\u6709\u8fb9\u6309\u7167a\u7684\u5927\u5c0f\u6392\u5e8f\uff0c\u7136\u540e\u5c06b\u8282\u70b9\u4f5c\u4e3a\u5173\u952e\u5b57\uff0c\u8dd1\u52a8\u6001\u52a0\u8fb9SPFA\u3002\n\u7136\u540e\u7b54\u6848\u5bf9dis[n]+e[i].a\u53bbmin\u5373\u53ef\u3002\u8fd9\u662f\u56e0\u4e3a\u5982\u679c\u5b83\u6ca1\u6709\u5f71\u54cd\u539f\u6765\u7684\u6700\u77ed\u8def\uff0c\u90a3\u4e48\u9009\u62e9\u8fd9\u6761\u8fb9\u7684a\u80af\u5b9a\u4e0d\u4f1a\u66f4\u4f18\uff1b\u5982\u679c\u66f4\u65b0\u4e86\uff0c\u90a3\u4e48\u5c31\u5fc5\u987b\u8981\u9009\u62e9\u8fd9\u6761\u8fb9\u7684a\u3002\n\u590d\u6742\u5ea6\u5927\u6982\u662f\u677e\u677e\u677e\uff0c\u6784\u9020\u4e86\u83ca\u82b1\u5957\u83ca\u82b1\u4e5f\u6ca1\u6709\u5361\u6389\uff0c\u5c31\u5047\u88c5\u80fd\u8fc7\u5427…\u6c42\u5927\u4f6c\u8bc1\u660e\u3002<\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\nconst int N=50005;\nconst int INF=0x3f3f3f3f;\nstruct ee{\n\tint v;\n\tint w;\n\tint nxt;\n}e[200005];\nstruct data{\n\tint u;int v;int a;int b;\n\tinline bool operator<(const data &B){\n\t\treturn a^B.a?a<B.a:b<B.b;\n\t}\n}ed[100005];\nint h[N],et=0;\ninline void Eadd(int U,int V,int W){\n\te[++et]=(ee){V,W,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V,int W){\n\tEadd(U,V,W),Eadd(V,U,W);\n}\nint dis[N];\nbool vis[N];\nqueue<int> q;\ninline void SPFA(int s1,int s2){\n\tvis[s1]=vis[s2]=1;\n\tq.push(s1),q.push(s2);\n\tint p;\n\twhile(!q.empty()){\n\t\tp=q.front();q.pop();\n\t\tfor(int i=h[p];i;i=e[i].nxt){\n\t\t\tif(Max(dis[p],e[i].w)<dis[e[i].v]){\n\t\t\t\tdis[e[i].v]=Max(dis[p],e[i].w);\n\t\t\t\tif(!vis[e[i].v]){\n\t\t\t\t\tvis[e[i].v]=1;\n\t\t\t\t\tq.push(e[i].v);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tvis[p]=0;\n\t}\n}\nint n,m;\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tfor(int i=2;i<=n;++i){\n\t\tdis[i]=INF;\n\t}\n\tfor(int i=1;i<=m;++i){\n\t\tscanf(\"%d%d%d%d\",&ed[i].u,&ed[i].v,&ed[i].a,&ed[i].b);\n\t}\n\tsort(ed+1,ed+1+m);\n\tint ans=INF;\n\tfor(int i=1;i<=m;++i){\n\t\tadd(ed[i].u,ed[i].v,ed[i].b);\n\t\tSPFA(ed[i].u,ed[i].v);\n\t\tans=Min(ans,dis[n]+ed[i].a);\n\t}\n\tprintf(\"%d\\n\",ans<INF?ans:-1);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u4e00\u9898\u636e\u8bf4\u662fLCT\u7ef4\u62a4\u8fb9\u6743\u7684\u9898\u76ee\u3002\u4f46\u662f\u6211\u4eec\u89c2\u5bdf\u4e00\u4e0b\u611f\u89c9\u53ef\u4ee5\u7528\u52a8\u6001\u52a0\u8fb9SPFA\u6765\u8dd1\u8fd9\u9053\u9898\u3002 \u5177\u4f53\u6765\u8bf4\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u6761 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp2387 NOI2014 \u9b54\u6cd5\u68ee\u6797\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[50,107,30,31,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/856"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=856"}],"version-history":[{"count":2,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/856\/revisions"}],"predecessor-version":[{"id":869,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/856\/revisions\/869"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=856"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}