{"id":68,"date":"2016-09-20T13:35:22","date_gmt":"2016-09-20T05:35:22","guid":{"rendered":"http:\/\/tyswly.com\/?p=68"},"modified":"2016-09-20T13:35:22","modified_gmt":"2016-09-20T05:35:22","slug":"noip2014%e5%af%bb%e6%89%be%e9%81%93%e8%b7%af","status":"publish","type":"post","link":"https:\/\/tys.fun\/?p=68","title":{"rendered":"[NOIP2014]\u5bfb\u627e\u9053\u8def"},"content":{"rendered":"<p>\u9898\u9762\u89c1<a href=\"http:\/\/cojs.tk\/cogs\/problem\/problem.php?pid=1807\">COGS<\/a><br \/>\n\u554a\u554a\u554a\u554a\u554a\u554a\u554a\u554a\u554a\uff0c\u88ab\u8fd9\u5927\u6c34\u9898\u5361\u4e86\u4e00\u5929\uff08\u8fd9\u662f\u8981\u586b\u6628\u5929\u7684\u5751\u7684\u535a\u6587\uff09\uff0c\u6211\u679c\u7136\u8fd8\u662f\u592a\u5f31\u554a\u3002<br \/>\n\u8fd9\u4e48\u6c34\u7684\u9898\uff0c\u53ea\u7528\u6b63\u53cd\u4e24\u904dBFS\u5c31\u597d\u4e86\uff0c\u76f4\u63a5\u8d34\u4ee3\u7801\uff0c<del>\u4e00\u5982\u65e2\u5f80\u5730\u6ca1\u6709\u6ce8\u91ca\u3002<\/del><\/p>\n<pre class=\"lang:c++ decode:true\">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;queue&gt;\n#include &lt;cstring&gt;\nusing namespace std;\nconst int MXM = 200005;\nconst int MXN = 10005;\nint head[MXN], head2[MXN], tot, s, t, m, n;\nint dis[MXN];\nbool ok[MXN], can[MXN];\nstruct edge{\n\tint fr, to, ne;\n}e[MXM], e2[MXM];\nvoid addedge(int a, int b) {\n\ttot++;\n\te[tot].fr = a;\n\te2[tot].fr = b;\n\te[tot].to = b;\n\te2[tot].to = a;\n\te[tot].ne = head[a];\n\thead[a] = tot;\n\te2[tot].ne = head2[b];\n\thead2[b] = tot;\n}\nbool vis[MXN];\nvoid bfs1() {\n\tqueue &lt;int&gt; q;\n\tq.push(t);\n\tcan[t] = true;\n\twhile (!q.empty()) {\n\t\tint now = q.front();\n\t\tq.pop();\n\t\tfor (int i = head2[now]; i; i = e2[i].ne) {\n\t\t\tint to = e2[i].to;\n\t\t\tif (!vis[to]) {\n\t\t\t\tcan[to] = true;\n\t\t\t\tvis[to] = true;\n\t\t\t\tq.push(to);\n\t\t\t}\n\t\t}\n\t}\n\tmemset(vis, 0, sizeof(vis));\n}\nvoid bfs2() {\n\tqueue &lt;int&gt; q;\n\tq.push(s);\n\twhile (!q.empty()) {\n\t\tint now = q.front();\n\t\tq.pop();\n\t\tfor (int i = head[now]; i; i = e[i].ne) {\n\t\t\tint to = e[i].to;\n\t\t\tif (!vis[to]) {\n\t\t\t\tif (ok[to]) {\n\t\t\t\t\tdis[to] = dis[now] + 1;\n\t\t\t\t\tq.push(to);\n\t\t\t\t}\n\t\t\t\tvis[to] = true;\n\t\t\t}\n\t\t}\n\t}\n}\nint main() {\n\t\/\/freopen(\"roadb.in\", \"r\", stdin);\n\t\/\/freopen(\"roadb.out\", \"w\", stdout);\n\tscanf(\"%d%d\", &amp;n, &amp;m);\n\tint x, y;\n\tfor (int i = 1; i &lt;= m; i++) {\n\t\tscanf(\"%d%d\", &amp;x, &amp;y);\n\t\taddedge(x, y);\n\t}\n\tscanf(\"%d%d\", &amp;s, &amp;t);\n\tbfs1();\n\tmemset(ok, 1, sizeof(ok));\n\tqueue &lt;int&gt; q;\n\tq.push(s);\n\twhile (!q.empty()) {\n\t\tint now = q.front();\n\t\tq.pop();\n\t\tfor (int i = head[now]; i; i = e[i].ne) {\n\t\t\tint to = e[i].to;\n\t\t\tif (!can[e[i].to]) {\n\t\t\t\tok[e[i].fr] = false;\n\t\t\t}\n\t\t\tif (!vis[to]) {\n\t\t\t\tvis[to] = true;\n\t\t\t\tq.push(to);\n\t\t\t}\n\t\t}\n\t}\n\tif (!ok[s]) {\n\t\tprintf(\"-1\\n\");\n\t\treturn 0;\n\t}\n\tmemset(vis, 0, sizeof(vis));\n\tbfs2();\n\tif (!dis[t]) {\n\t\tprintf(\"-1\\n\");\n\t\treturn 0;\n\t}\n\tprintf(\"%d\\n\", dis[t]);\n\treturn 0;\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u9762\u89c1COGS \u554a\u554a\u554a\u554a\u554a\u554a\u554a\u554a\u554a\uff0c\u88ab\u8fd9\u5927\u6c34\u9898\u5361\u4e86\u4e00\u5929\uff08\u8fd9\u662f\u8981\u586b\u6628\u5929\u7684\u5751\u7684\u535a\u6587\uff09\uff0c\u6211\u679c\u7136\u8fd8\u662f\u592a\u5f31\u554a\u3002 \u8fd9\u4e48\u6c34\u7684 &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-68","post","type-post","status-publish","format-standard","hentry","category-report"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/68","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=68"}],"version-history":[{"count":0,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/68\/revisions"}],"wp:attachment":[{"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=68"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=68"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=68"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}