{"id":328501,"date":"2022-01-24T15:00:34","date_gmt":"2022-01-24T15:00:34","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=328501"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=328501","title":{"rendered":"<span>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. \u0420\u0430\u0437\u0431\u043e\u0440 \u0417\u0430\u0434\u0430\u0447<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><img decoding=\"async\" src=\"\/img\/image-loader.svg\" data-src=\"https:\/\/habrastorage.org\/webt\/nz\/pb\/w3\/nzpbw391_h_aqdzjdygc_n0tcfk.png\"\/><\/p>\n<p>  \u041f\u043e\u0438\u0441\u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435. \u0422\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0447\u0430\u0441\u0442\u043e \u0438 \u0432 \u043f\u043e\u0432\u0441\u0435\u0434\u043d\u0435\u0432\u043d\u043e\u0439 \u0436\u0438\u0437\u043d\u0438, \u0438 \u0432 \u043c\u0438\u0440\u0435 \u0442\u0435\u0445\u043d\u043e\u043b\u043e\u0433\u0438\u0439. \u0421\u043f\u0440\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u0441 \u0442\u0430\u043a\u0438\u043c\u0438 \u0432\u044b\u0437\u043e\u0432\u0430\u043c\u0438 \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0432 \u0430\u0440\u0441\u0435\u043d\u0430\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u0430 \u2014 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. <\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u043d\u0430\u0439\u0442\u0438 \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441\u044b, \u0447\u0435\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043b\u0443\u0447\u0448\u0435 BFS (\u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443), \u043f\u0440\u0438 \u043a\u0430\u043a\u0438\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c, \u0438 \u043a\u0430\u043a\u0438\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0438 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u043d\u043e \u0441 \u0435\u0433\u043e \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0440\u0435\u0448\u0430\u0442\u044c, \u0447\u0438\u0442\u0430\u0439\u0442\u0435 \u0434\u0430\u043b\u0435\u0435.<\/p>\n<p>  <a name=\"habracut\"><\/a><\/p>\n<h3>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h3>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 (\u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f\u043c\u0438 \u0438 \u043d\u0430 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445) \u0433\u0440\u0430\u0444\u0430\u0445, \u0438 \u043f\u0440\u0438\u0437\u0432\u0430\u043d \u0438\u0441\u043a\u0430\u0442\u044c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439 \u0438 \u0432\u0441\u0435\u043c\u0438 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435. <\/p>\n<p>  \u041a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0433\u0440\u0430\u0444 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0442 \u043a\u0430\u043a \u043d\u0430\u0431\u043e\u0440 \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0440\u0451\u0431\u0435\u0440 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/9d5\/044\/bb6\/9d5044bb6512f2704573edf47a00c3a6.svg\" alt=\"\\inline G = (V,E),\"\/> \u0433\u0434\u0435 \u0447\u0438\u0441\u043b\u043e \u0440\u0451\u0431\u0435\u0440 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u0430\u0434\u0430\u043d\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/434\/f4e\/96e\/434f4e96e4211a7a64e4fc39b2279d1f.svg\" alt=\"\\inline m\"\/>, \u0430 \u0432\u0435\u0440\u0448\u0438\u043d \u0447\u0438\u0441\u043b\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/cac\/f47\/d62\/cacf47d625fe8b7e7b6874fde25d9c9c.svg\" alt=\"\\inline n.\"\/><\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0435\u0431\u0440\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0437\u0430\u0434\u0430\u043d <i>\u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441<\/i> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ab1\/8d0\/6ef\/ab18d06efbc152b57614bb847b4f60ba.svg\" alt=\"\\inline l_i\"\/>, \u0430 \u0442\u0430\u043a\u0436\u0435 <i>\u0432\u0435\u0440\u0448\u0438\u043d\u0430<\/i>, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0438\u0441\u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0443\u0442\u0435\u0439.<\/p>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/a45\/151\/0e4\/a451510e45634fc77be856d93cc43e03.svg\" alt=\"\\inline s\"\/> \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/18b\/72f\/d1c\/18b72fd1c6138b75d69afa93b6c4b3f7.svg\" alt=\"\\inline t\"\/> \u0432 \u0433\u0440\u0430\u0444\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u0438\u043d \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u044d\u0442\u0438\u043c\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f, \u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e, \u0432\u0435\u0440\u043d\u0443\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 &#171;\u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c&#187; \u0434\u043b\u044f \u043f\u0430\u0440\u044b \u043d\u0435\u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d.<\/p>\n<p>  <\/p>\n<p>\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432\u0435\u0441\u043e\u0432 \u0440\u0451\u0431\u0435\u0440 \u043a\u0440\u0430\u0439\u043d\u0435 \u0432\u0430\u0436\u043d\u043e \u0438 \u043e\u0442 \u043d\u0435\u0433\u043e \u043d\u0435\u043b\u044c\u0437\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f. \u041d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0441\u0432\u0435\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0440\u0435\u0448\u0430\u0435\u043c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0432 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0432\u0435\u0441 \u043a\u043e \u0432\u0441\u0435\u043c \u0440\u0451\u0431\u0440\u0430\u043c. \u042d\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442. \u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0432 \u043f\u0435\u0440\u0432\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c7e\/e87\/146\/c7ee87146ab3822d1efedb85d50677d4.svg\" alt=\"\\inline a\"\/> \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/848\/9a3\/a54\/8489a3a54e79d8e152f4973a92513841.svg\" alt=\"\\inline d\"\/> (\u0441\u0443\u043c\u043c\u0430 \u0440\u0451\u0431\u0435\u0440 \u043d\u0430 \u043f\u0443\u0442\u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0430\u044f) \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u0442\u0430\u043a\u043e\u0439 \u043c\u0430\u043d\u0438\u043f\u0443\u043b\u044f\u0446\u0438\u0438. \u0412 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0435 \u043f\u0443\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u0447\u0435\u0440\u0435\u0437 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/e6f\/a5d\/5d2\/e6fa5d5d2066f82f89fba2e536389000.svg\" alt=\"\\inline a \\rightarrow b \\rightarrow c \\rightarrow d\"\/>, \u0430 \u043f\u043e\u0441\u043b\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u0435\u043c\u0451\u0440\u043a\u0438 \u043a\u043e \u0432\u0441\u0435\u043c \u0440\u0451\u0431\u0440\u0430\u043c, \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u0447\u0435\u0440\u0435\u0437 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/4ef\/091\/b47\/4ef091b47c76b0241d729724869bfaa8.svg\" alt=\"\\inline a \\rightarrow c \\rightarrow d.\"\/><\/p>\n<p>  <img decoding=\"async\" src=\"\/img\/image-loader.svg\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/442\/9c0\/74f\/4429c074f7c6c7cc02aa52fb98033282.png\"\/>  <\/p>\n<p>\u041a\u0430\u043a \u0432\u0435\u0434\u0451\u0442 \u0441\u0435\u0431\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435, \u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c, \u043a\u043e\u0433\u0434\u0430 \u0432\u044b\u043f\u0438\u0448\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041d\u043e \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0437\u0430\u0434\u0430\u0434\u0438\u043c\u0441\u044f \u0434\u0440\u0443\u0433\u0438\u043c \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c: &#171;\u043f\u043e\u0447\u0435\u043c\u0443 \u043d\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0433\u0440\u0430\u0444\u0430?&#187;. \u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u043c\u0435\u0442\u043e\u0434 BFS \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432 \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u0434\u043e \u043b\u044e\u0431\u043e\u0439 \u0434\u0440\u0443\u0433\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043d\u043e \u044d\u0442\u043e \u0441\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0440\u0451\u0431\u0435\u0440 \u0441 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u043c \u0432\u0435\u0441\u043e\u043c.<\/p>\n<p>  <\/p>\n<p>\u0421\u0432\u0435\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0440\u0435\u0448\u0430\u0435\u043c\u043e\u0439 BFS \u043c\u043e\u0436\u043d\u043e, \u043d\u043e \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0440\u0451\u0431\u0440\u0430 \u043d\u0435\u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/295\/5b5\/154\/2955b515455bac46be7f365cadb3a78d.svg\" alt=\"\\inline n\"\/> \u0440\u0451\u0431\u0440\u0430\u043c\u0438 \u0434\u043b\u0438\u043d\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c0d\/19f\/f35\/c0d19ff352c83e25f4688082b3f861ed.svg\" alt=\"\\inline 1\"\/>, \u0442\u043e \u0433\u0440\u0430\u0444 \u043e\u0447\u0435\u043d\u044c \u0440\u0430\u0437\u0440\u0430\u0441\u0442\u0451\u0442\u0441\u044f, \u0438 \u044d\u0442\u043e \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u0442 \u043a \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439 \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430.<\/p>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u044d\u0442\u043e\u0433\u043e \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. \u041e\u043f\u0438\u0448\u0435\u043c \u0435\u0433\u043e:<\/p>\n<p>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0417\u0430\u0434\u0430\u0451\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ff9\/b74\/239\/ff9b742394b7fe76b20b23bf904f7479.svg\" alt=\"\\inline X = \\{s\\}\"\/>, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/li>\n<li>\u041c\u0430\u0441\u0441\u0438\u0432 \u0434\u043b\u0438\u043d \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u043f\u0443\u0442\u0435\u0439 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/b29\/a57\/71e\/b29a5771eb050d1c6e1603f198ea9938.svg\" alt=\"\\inline A\"\/>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0435\u0441\u0442\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/cbe\/d20\/970\/cbed209704fee35fac53489d95a5d7e7.svg\" alt=\"\\inline A[s] = 0\"\/>, \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u043f\u0443\u0442\u044c \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u043e \u0441\u0435\u0431\u044f \u0441\u0430\u043c\u043e\u0439.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0439 \u0446\u0438\u043a\u043b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043d\u0435 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u044b (\u0438\u043b\u0438 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/a78\/a21\/275\/a78a2127562c3e93adcbd3ea1cf06828.svg\" alt=\"\\inline X \\neq V\"\/>), \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c:<br \/> \n<ul>\n<li>\u0421\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0440\u0451\u0431\u0435\u0440 \u0432 \u0433\u0440\u0430\u0444\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/fba\/4a6\/411\/fba4a641123e162591c586e319f8c64e.svg\" alt=\"\\inline (v,w)\"\/> \u0442\u0430\u043a\u0438\u0445, \u0447\u0442\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/856\/d00\/98e\/856d0098ede714c478374c9f5ea8aa9b.svg\" alt=\"\\inline v \\in X\"\/>, \u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/f57\/9f3\/1eb\/f579f31ebdf543c1c9f395937f8e0c52.svg\" alt=\"\\inline w \\notin X\"\/>, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043e\u0434\u043d\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u0441\u0443\u043c\u043c\u0443: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/5f4\/941\/d3a\/5f4941d3a0b1a923894e1fd878b8ea4f.svg\" alt=\"\\inline A[v] + l_{vw}.\"\/><\/li>\n<li>\u0414\u043e\u0431\u0430\u0432\u044f\u0435\u043c \u044d\u0442\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ed3\/df4\/ad8\/ed3df4ad8965fc52f903db54caae4e58.svg\" alt=\"\\inline w\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/729\/835\/318\/729835318244444e9f8bdc467df4e82c.svg\" alt=\"\\inline X\"\/>.<\/li>\n<li>\u0417\u0430\u0434\u0430\u0451\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6c4\/941\/9be\/6c49419befb39bf2af493bc6c3484ca2.svg\" alt=\"\\inline A[w]\"\/> \u0440\u0430\u0432\u043d\u044b\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/de4\/5ae\/0b2\/de45ae0b277e19c1b89dc99b8083faea.svg\" alt=\"\\inline A[v] + l_\\{vw\\}.\"\/><\/li>\n<\/ul>\n<p>  <\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435 \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043c\u0430\u0441\u0441\u0438\u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/b29\/a57\/71e\/b29a5771eb050d1c6e1603f198ea9938.svg\" alt=\"\\inline A\"\/> \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0432\u0441\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0443\u0442\u0438, \u0438\u0441\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0438\u0437 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/a45\/151\/0e4\/a451510e45634fc77be856d93cc43e03.svg\" alt=\"\\inline s\"\/>.<\/p>\n<h3>\u041f\u0440\u0438\u043c\u0435\u0440\u044b \u0440\u0430\u0431\u043e\u0442\u044b<\/h3>\n<p>  <img decoding=\"async\" src=\"\/img\/image-loader.svg\" alt=\"image\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/b63\/bad\/038\/b63bad0388dabb9b1ff2ba03db276c7c.png\"\/><\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0433\u0440\u0430\u0444 \u0432\u044b\u0448\u0435, \u0432 \u043d\u0451\u043c \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u043f\u0443\u0442\u0438 \u043e\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c7e\/e87\/146\/c7ee87146ab3822d1efedb85d50677d4.svg\" alt=\"\\inline a\"\/> \u0434\u043e \u0432\u0441\u0435\u0433\u043e \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u0433\u043e.<\/p>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0432\u044b\u0439 \u0448\u0430\u0433 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442, \u0447\u0442\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/465\/ae1\/ef7\/465ae1ef7aa126ad9baf723e98bb7d88.svg\" alt=\"\\inline b\"\/> \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043f\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0441\u0438\u043d\u0435\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0438 \u0438 \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c. \u0412\u0442\u043e\u0440\u043e\u0439 \u0448\u0430\u0433 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u0442, \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c10\/6ca\/2df\/c106ca2df0651dd2d791b59d6959e8fb.svg\" alt=\"\\inline A[v] + l_{vw}\"\/> \u0438 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432\u0434\u043e\u043b\u044c \u043a\u0440\u0430\u0441\u043d\u043e\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/e14\/8d9\/2f5\/e148d92f5372915a4cdbb51cd4921f3c.svg\" alt=\"\\inline 5\"\/> \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/b23\/5f2\/a61\/b235f2a61e6acee7b20b964e30eff0c1.svg\" alt=\"\\inline 3 + 3 = 6\"\/> \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/274\/c61\/eab\/274c61eab3060d9e2c026566bf503db7.svg\" alt=\"\\inline 3 + 6 = 9.\"\/> \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u0438\u043d\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ba1\/179\/6e9\/ba11796e9f26add64a89c0465baa3834.svg\" alt=\"\\inline c\"\/>. \u0418 \u043d\u0430\u043a\u043e\u043d\u0435\u0446, \u0442\u0440\u0435\u0442\u044c\u0438\u043c \u0448\u0430\u0433\u043e\u043c, \u043a\u043e\u0433\u0434\u0430 \u0442\u0440\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/39d\/380\/e17\/39d380e1791e51d5d1229ed5692ecbb9.svg\" alt=\"\\inline a,b,c\"\/> \u0443\u0436\u0435 \u043b\u0435\u0436\u0430\u0442 \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/729\/835\/318\/729835318244444e9f8bdc467df4e82c.svg\" alt=\"\\inline X\"\/>, \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0430 \u0440\u0435\u0431\u0440\u0430 \u0438 \u0432\u044b\u0431\u0440\u0430\u0442\u044c, \u043b\u0435\u0436\u0430\u0449\u0435\u0435 \u0432\u0434\u043e\u043b\u044c \u0437\u0435\u043b\u0435\u043d\u043e\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0438.<\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0433\u0440\u0430\u0444 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0432\u0435\u0441\u0430\u043c\u0438, \u0443\u043f\u043e\u043c\u044f\u043d\u0443\u0442\u044b\u0439 \u0432\u044b\u0448\u0435. \u041d\u0430\u043f\u043e\u043c\u043d\u044e, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u043d\u0430 \u0442\u0430\u043a\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0435\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e.<\/p>\n<p>  <img decoding=\"async\" src=\"\/img\/image-loader.svg\" alt=\"image\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ea2\/3f8\/3e6\/ea23f83e628dd268594da939143002ce.png\"\/><\/p>\n<p>\u041f\u0435\u0440\u0432\u044b\u043c \u0448\u0430\u0433\u043e\u043c \u043e\u0442\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e \u0432\u0434\u043e\u043b\u044c \u0441\u0438\u043d\u0435\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u044d\u0442\u043e \u0440\u0435\u0431\u0440\u043e \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0432\u0435\u0441\u0430 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u0417\u0430\u0442\u0435\u043c \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/0d9\/60d\/3b3\/0d960d3b346db10fbca8dc925ca90958.svg\" alt=\"\\inline c \\rightarrow d.\"\/> \u042d\u0442\u043e \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u0442 \u043d\u0430\u0432\u0441\u0435\u0433\u0434\u0430 \u043d\u0435\u0432\u0435\u0440\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c7e\/e87\/146\/c7ee87146ab3822d1efedb85d50677d4.svg\" alt=\"\\inline a\"\/> \u043a <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/848\/9a3\/a54\/8489a3a54e79d8e152f4973a92513841.svg\" alt=\"\\inline d\"\/>, \u0432 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u0447\u0435\u0440\u0435\u0437 \u0446\u0435\u043d\u0442\u0440 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0432\u0435\u0441\u043e\u043c. \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u0448\u0430\u0433\u043e\u043c, \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/465\/ae1\/ef7\/465ae1ef7aa126ad9baf723e98bb7d88.svg\" alt=\"\\inline b\"\/>.<\/p>\n<h3>\u041e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h3>\n<p>\u041a \u044d\u0442\u043e\u043c\u0443 \u043c\u043e\u043c\u0435\u043d\u0442\u0443 \u043c\u044b \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438 \u0441\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u043d\u0430\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u043c\u044b\u0435 \u043d\u0430 \u0435\u0433\u043e \u0440\u0430\u0431\u043e\u0442\u0443 \u0438 \u0440\u044f\u0434 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0443\u043f\u043e\u043c\u044f\u043d\u0435\u043c \u043a\u0430\u043a\u043e\u0432\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u044d\u0442\u043e \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u0442\u0441\u044f \u043d\u0430\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447, \u0440\u0430\u0434\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u0442\u0435\u0432\u0430\u043b\u0430\u0441\u044c \u044d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f.<br \/>  \u0411\u0430\u0437\u043e\u0432\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u0446\u0438\u043a\u043b\u0430\u0445, \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442 \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u0432\u0441\u0435\u043c \u0440\u0451\u0431\u0440\u0430\u043c \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0447\u0442\u043e \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/82a\/efe\/eed\/82aefeeed553dab537f6c983a1ecbc8a.svg\" alt=\"\\inline \\theta(mn)\"\/>.<\/p>\n<p>  <\/p>\n<p>\u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u0443\u0447\u0438. \u041e\u0431 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043a\u043e\u0440\u043e\u0442\u043a\u043e: \u043e\u043d\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0434\u0432\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u041f\u0435\u0440\u0432\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u2014 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u0443\u0437\u043b\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u043a\u043b\u044e\u0447\u043e\u043c, \u0438, \u0432\u0442\u043e\u0440\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f, \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u043d\u043e\u0432\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c.<\/p>\n<p>  <\/p>\n<p>\u0427\u0442\u043e \u0435\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043e \u043a\u0443\u0447\u0435:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u044d\u0442\u043e \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e,<\/li>\n<li>\u043a\u043b\u044e\u0447 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u043b\u0438\u0431\u043e \u0440\u0430\u0432\u0435\u043d \u043a\u043b\u044e\u0447\u0435\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432.<\/li>\n<\/ul>\n<p>  <\/p>\n<blockquote><p> \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u0443\u0447 \u044f \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u043b \u0440\u0430\u043d\u0435\u0435 \u0432 \u044d\u0442\u043e\u043c <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/565988\/\">\u043f\u043e\u0441\u0442\u0435<\/a>.<\/p><\/blockquote>\n<p>  <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043a\u0443\u0447\u0443 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0433\u0434\u0435 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043b\u044e\u0447\u0435\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432 \u043d\u0435\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0433\u0440\u0430\u0444\u0430 (\u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u044d\u0442\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/2b5\/370\/39a\/2b537039a6ce9cbf018ffeb12bf0a057.svg\" alt=\"\\inline V-X\"\/>), \u0434\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0432 \u0443\u0436\u0435 \u043f\u043e\u043a\u0440\u044b\u0442\u043e\u043c (\u044d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/729\/835\/318\/729835318244444e9f8bdc467df4e82c.svg\" alt=\"\\inline X\"\/>), \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0434\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/723\/107\/114\/7231071142d1fe65f5ff089322ffc783.svg\" alt=\"\\inline O(m\\log(n)).\"\/> \u0414\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e \u0441\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u043e\u0441\u0442\u0438 \u044d\u0442\u0438\u0445 \u043e\u0446\u0435\u043d\u043e\u043a \u044f \u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u043c\u0438 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438.<\/p>\n<p>  <\/p>\n<p>\u0414\u0430\u043b\u0435\u0435 \u043f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043a \u0440\u0430\u0437\u0431\u043e\u0440\u0443 \u0437\u0430\u0434\u0430\u0447!<\/p>\n<h3>\u0417\u0430\u0434\u0430\u0447\u0430 \u21161<\/h3>\n<p>\u0411\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c <i>\u0443\u0437\u043a\u0438\u043c \u043c\u0435\u0441\u0442\u043e\u043c<\/i> \u043f\u0443\u0442\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0440\u0435\u0431\u0440\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0432 \u044d\u0442\u043e\u043c \u043f\u0443\u0442\u0438. \u041f\u0443\u0442\u0451\u043c \u0441 <i>\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0443\u0437\u043a\u0438\u043c \u043c\u0435\u0441\u0442\u043e\u043c<\/i> \u043d\u0430\u0437\u043e\u0432\u0451\u043c \u0442\u0430\u043a\u043e\u0439 \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/a45\/151\/0e4\/a451510e45634fc77be856d93cc43e03.svg\" alt=\"s\"\/> \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/18b\/72f\/d1c\/18b72fd1c6138b75d69afa93b6c4b3f7.svg\" alt=\"t\"\/>, \u0447\u0442\u043e \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u043f\u0443\u0442\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/798\/c93\/70e\/798c9370e9eb55a7ed8b73338413d48e.svg\" alt=\"s \\rightarrow t\"\/>, \u0447\u044c\u0451 \u0443\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u043e \u0434\u043b\u0438\u043d\u0435. \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043f\u0443\u0442\u044c \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0443\u0437\u043a\u0438\u043c \u043c\u0435\u0441\u0442\u043e\u043c \u0434\u043b\u044f \u0434\u0432\u0443\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d \u0432 \u0433\u0440\u0430\u0444\u0435. \u0410\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/247\/af1\/86c\/247af186cb6d1d1ff1cdc21a710143ec.svg\" alt=\"O(m\\log{n})\"\/><\/p>\n<h3>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h3>\n<p>\u041f\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u044e \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0435\u0431\u0440\u043e \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0432\u0435\u0441\u043e\u043c \u0442\u0440\u0430\u043a\u0442\u0443\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0443\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e. \u0412\u0435\u0441 \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u043a\u0430\u043a \u0446\u0435\u043d\u0443 \u0437\u0430 \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u0440\u0435\u0431\u0440\u0443. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u0439 \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u044b \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b, \u0435\u0441\u043b\u0438 \u043c\u044b \u0437\u0430\u0445\u043e\u0442\u0438\u043c \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u043b\u044e\u0431\u043e\u0439 \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u0443\u0442\u044c, \u043e\u043d \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0442\u044f\u0436\u0435\u043b\u044b\u0435 \u0440\u0451\u0431\u0440\u0430.<\/p>\n<p>  <\/p>\n<p>\u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438, \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430, \u043c\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u043c \u0432 \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0433\u0440\u0430\u0444\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0434\u043b\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 \u0434\u043e \u044d\u0442\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u0417\u0434\u0435\u0441\u044c \u0441\u0442\u043e\u0438\u0442 \u043e\u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0431\u0443\u0434\u0435\u043c \u0438\u043c\u0435\u043d\u043e\u0432\u0430\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/729\/835\/318\/729835318244444e9f8bdc467df4e82c.svg\" alt=\"X\"\/> \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u043c\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438, \u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/2b5\/370\/39a\/2b537039a6ce9cbf018ffeb12bf0a057.svg\" alt=\"V - X\"\/> \u0447\u0430\u0441\u0442\u044c \u0433\u0440\u0430\u0444\u0430, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0435\u0449\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 \u0438\u043b\u0438 \u0443\u0437\u043a\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430.<\/p>\n<p>  <\/p>\n<p>\u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u043e\u043b\u0436\u043d\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043a\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u043f\u0443\u0442\u0438, \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0435\u0433\u043e \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/856\/d00\/98e\/856d0098ede714c478374c9f5ea8aa9b.svg\" alt=\"v \\in X\"\/>. \u0410 \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u043d\u043e\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438\u0437 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/2b5\/370\/39a\/2b537039a6ce9cbf018ffeb12bf0a057.svg\" alt=\"V - X\"\/>, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u043b\u0438 \u0440\u0435\u0431\u0440\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/646\/b53\/fba\/646b53fbaaa2252ce3a6ef8e7bdc5b04.svg\" alt=\"(v,u_1)\"\/> \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443 \u0443\u0437\u043a\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u043f\u0443\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/63d\/d83\/c84\/63dd83c84973b09630a9639ed6871031.svg\" alt=\"u_1\"\/>.<br \/>  \u0415\u0441\u043b\u0438 \u0440\u0435\u0431\u0440\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/646\/b53\/fba\/646b53fbaaa2252ce3a6ef8e7bdc5b04.svg\" alt=\"(v, u_1)\"\/> \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0443\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0442\u043e \u043b\u0443\u0447\u0448\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u0443 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/8e3\/d20\/eb1\/8e3d20eb1163143917e3eff4ba46a312.svg\" alt=\"u_2\"\/>, \u0440\u0435\u0431\u0440\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/31a\/536\/1d5\/31a5361d580f26995c5fae50a25de65b.svg\" alt=\"(v, u_2)\"\/> \u0434\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043b\u0435\u0433\u0447\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/646\/b53\/fba\/646b53fbaaa2252ce3a6ef8e7bdc5b04.svg\" alt=\"(v,u_1)\"\/>. \u041f\u043e\u0438\u0441\u043a \u043d\u0435\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0445 \u0443\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u0440\u0435\u0431\u0451\u0440 \u043d\u0443\u0436\u043d\u043e \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0440\u0435\u0434\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c16\/316\/221\/c16316221409a75e305587a71365a3ff.svg\" alt=\"v\"\/>, \u043d\u043e \u0438 \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/856\/d00\/98e\/856d0098ede714c478374c9f5ea8aa9b.svg\" alt=\"v \\in X\"\/>, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u0442\u0434\u0430\u0432\u0430\u044f \u043f\u0440\u0435\u0434\u043f\u043e\u0447\u0442\u0435\u043d\u0438\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u0435, \u043f\u0443\u0442\u044c \u0432 \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0438\u043c\u0435\u0435\u0442 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0443\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u0432 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442, \u043c\u044b \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u043c, \u0447\u0442\u043e \u043c\u044b \u043d\u0435 \u0443\u0445\u0443\u0434\u0448\u0430\u0435\u043c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u0434\u043b\u044f \u0434\u0440\u0443\u0433\u0438\u0445 \u0432\u0435\u0440\u0448\u0438\u043d.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u043c: \u0435\u0441\u043b\u0438 \u043f\u0443\u0442\u044c, \u043e\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/bbe\/114\/782\/bbe11478277838a7ae6fb7ad71168188.svg\" alt=\"p\"\/> \u0438\u043c\u0435\u0435\u0442 \u0443\u0437\u043a\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/9c6\/80f\/d4f\/9c680fd4f66c8998dfe02a6bd327e318.svg\" alt=\"3\"\/>, \u0438 \u0435\u0441\u0442\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/487\/b0c\/0bc\/487b0c0bc946c8ef35554e29fd9aa954.svg\" alt=\"q\"\/> \u0441 \u0440\u0435\u0431\u0440\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/f20\/0f7\/855\/f200f7855dc39b492f4c4ac87ae8f202.svg\" alt=\"(p,q)\"\/> \u0432\u0435\u0441\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/022\/d90\/d99\/022d90d990d7a085eeaae0b8eeba83cf.svg\" alt=\"4\"\/>, \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/261\/8db\/949\/2618db9493da0489f59b386504cd36ca.svg\" alt=\"r\"\/> \u0441 \u0440\u0435\u0431\u0440\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/225\/a65\/be6\/225a65be6a489494f6e38b8906425f73.svg\" alt=\"(p,r)\"\/> \u0432\u0435\u0441\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/e14\/8d9\/2f5\/e148d92f5372915a4cdbb51cd4921f3c.svg\" alt=\"5\"\/>, \u0442\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u0447\u0442\u0435\u043d\u0438\u0435 \u043e\u0442\u0434\u0430\u0451\u0442\u0441\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/487\/b0c\/0bc\/487b0c0bc946c8ef35554e29fd9aa954.svg\" alt=\"q\"\/>, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u0430\u0441\u0442 \u0432\u0435\u0440\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u043e\u0431\u043e\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f, \u0435\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/7ef\/188\/dfd\/7ef188dfd261680e8355b30357456bfc.svg\" alt=\"(q,r)\"\/> \u0432\u0435\u0441\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/9c6\/80f\/d4f\/9c680fd4f66c8998dfe02a6bd327e318.svg\" alt=\"3\"\/> \u0438\u043b\u0438 \u0432\u0435\u0441\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/768\/c9f\/80c\/768c9f80ca4860049369bfdbf7bd4f34.svg\" alt=\"10\"\/>.<\/p>\n<p>  \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0432\u044b\u0448\u0435, \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u043e\u0439 \u043f\u0440\u0438 \u0432\u044b\u0431\u043e\u0440\u0435 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438\u0437 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0438 \u0432\u0435\u043b\u0438\u0447\u0438\u043d, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u043c.<\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6bf\/459\/cbd\/6bf459cbdc59a4ffaf8b7bfe68ed0f27.svg\" alt=\"A(u) = \\min_{v \\in X}\\left(\\max \\left[A(v), w\\left(v,u\\right)\\right]\\right), \\, u \\in V - X\"\/><\/div>\n<p>\u0421\u0442\u043e\u0438\u0442 \u043f\u043e\u044f\u0441\u043d\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u043e\u0438\u0441\u043a \u043f\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/856\/d00\/98e\/856d0098ede714c478374c9f5ea8aa9b.svg\" alt=\"v \\in X\"\/> \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f, \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0441\u0432\u044f\u0437\u0435\u0439 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/fb8\/e2f\/9b6\/fb8e2f9b615ee6385501546d6fb9025c.svg\" alt=\"(v,u),\"\/> \u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/5e6\/1b8\/020\/5e61b8020cd599d06b1d1b884c2c1056.svg\" alt=\"w(v,u) -\"\/> \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/1b0\/c4b\/924\/1b0c4b9243fb8cb706fe274ac282fd89.svg\" alt=\"(v,u)\"\/>.<\/p>\n<p>  <img decoding=\"async\" src=\"\/img\/image-loader.svg\" alt=\"image\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/82e\/68a\/5e7\/82e68a5e7ae78235b5c8f712db58c1b8.png\"\/><\/p>\n<h3>\u0417\u0430\u0434\u0430\u0447\u0430 \u21162<\/h3>\n<p>\u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0440\u0435\u0448\u0438\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443. \u041f\u0443\u0441\u0442\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/295\/5b5\/154\/2955b515455bac46be7f365cadb3a78d.svg\" alt=\"\\inline n\"\/> \u0433\u043e\u0440\u043e\u0434\u043e\u0432, \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043f\u0443\u0442\u0438, \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c <code>edges[i] = [city_a, city_b, distance_ab]<\/code>, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0434\u0430\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <code>mileage<\/code>.<\/p>\n<p>  <\/p>\n<p>\u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u043e\u0439 \u0433\u043e\u0440\u043e\u0434 \u0438\u0437 \u0434\u0430\u043d\u043d\u044b\u0445, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0441\u0438\u0432 <code>mileage<\/code>.<\/p>\n<p>  <\/p>\n<p>\u0421\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0433\u0440\u0430\u0444 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b\u0439, \u0442.\u0435. \u043f\u043e \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438 \u043c\u043e\u0436\u043d\u043e \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432 \u043e\u0431\u0435 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u0430 \u0434\u043b\u0438\u043d\u0430 \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438 <code>a<\/code> \u0438 <code>c<\/code> \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0430 \u043a\u0430\u043a \u0441\u0443\u043c\u043c\u0430 \u0434\u043b\u0438\u043d \u043f\u0443\u0442\u0435\u0439 <code>a -> b<\/code> \u0438 <code>b -> c<\/code>, \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u043c\u0430\u0440\u0448\u0440\u0443\u0442 <code>a -> b -> c<\/code><\/p>\n<h3>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h3>\n<p>\u0421 \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043d\u0430\u043c \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u0438 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u0430\u044f \u0432\u044b\u0448\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0443\u0447\u0438. \u041f\u043e\u0441\u0442\u0430\u0432\u0449\u0438\u043a\u043e\u043c \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u0442\u0430\u043d\u0435\u0442 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 <code>heapq<\/code> \u0432 Python.<\/p>\n<p>\u0411\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0433\u043e\u0440\u043e\u0434\u043e\u0432, \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u0435\u043d\u044c\u0448\u0435 <code>mileage<\/code>, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/295\/5b5\/154\/2955b515455bac46be7f365cadb3a78d.svg\" alt=\"\\inline n\"\/> \u0433\u043e\u0440\u043e\u0434\u043e\u0432. \u0421\u043e\u0431\u0435\u0440\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0432 \u0432 \u043e\u0434\u043d\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u0438 \u043d\u0430\u0439\u0434\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0438\u0437 \u043d\u0438\u0445.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043d\u0430\u0448 \u0433\u0440\u0430\u0444 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439, \u0442\u043e \u0438\u0437 \u043b\u044e\u0431\u043e\u0439 \u0435\u0433\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/a45\/151\/0e4\/a451510e45634fc77be856d93cc43e03.svg\" alt=\"\\inline s\"\/> \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/18b\/72f\/d1c\/18b72fd1c6138b75d69afa93b6c4b3f7.svg\" alt=\"\\inline t\"\/>. \u0411\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 \u0432 \u0433\u0440\u0430\u0444\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u043f\u0443\u0442\u0438 \u0434\u043e \u0432\u0441\u0435\u0445 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0433\u043e\u0440\u043e\u0434\u043e\u0432, \u043c\u044b \u044d\u0442\u043e \u0443\u0436\u0435 \u0443\u043c\u0435\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u0432 \u0442\u0435\u043e\u0440\u0438\u0438. \u0418 \u0447\u0442\u043e\u0431\u044b, \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441, \u0431\u0443\u0434\u0435\u043c \u0432 \u0435\u0433\u043e \u0442\u0435\u0447\u0435\u043d\u0438\u0438 \u0441\u0440\u0430\u0437\u0443 \u043e\u0442\u0432\u0435\u0440\u0433\u0430\u0442\u044c \u043f\u0443\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 <code>mileage<\/code>, \u0430 \u043d\u0435 \u0434\u0435\u043b\u0430\u0442\u044c \u043f\u043e\u0441\u0442\u0444\u0430\u043a\u0442\u0443\u043c, \u043a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u043f\u0443\u0442\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u044b.<\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u043f\u0438\u0448\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0440\u0435\u0448\u0435\u043d\u0438\u044f:<\/p>\n<pre><code class=\"python\">def least_reachable_city(n, edges, mileage):         \"\"\"         \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:             n --- \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0433\u043e\u0440\u043e\u0434\u043e\u0432,             edges --- \u0442\u0440\u043e\u0439\u043a\u0438 (a, b, distance_ab),             mileage --- \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438              \u0434\u043b\u044f \u0441\u043e\u0441\u0435\u0434\u0441\u0442\u0432\u0430         \"\"\"         # \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 (adjacency list), \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e          # \u0441\u043b\u043e\u0432\u0430\u0440\u044c, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u043b\u044e\u0447\u0438 \u044d\u0442\u043e \u0433\u043e\u0440\u043e\u0434\u0430, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f --- \u043f\u0430\u0440\u044b          # (&lt;\u0434\u0440\u0443\u0433\u043e\u0439_\u0433\u043e\u0440\u043e\u0434>, &lt;\u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435_\u0434\u043e_\u043d\u0435\u0433\u043e>)          graph = {}         for u, v, w in edges:             if graph.get(u, None) is None:                 graph[u] = [(v, w)]             else:                 graph[u].append((v, w))             if graph.get(v, None) is None:                 graph[v] = [(u, w)]             else:                 graph[v].append((u, w))                  # \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e \u043e\u0431\u044a\u044f\u0432\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u043f\u0443\u0442\u0438 \u0432          # \u0433\u0440\u0430\u0444\u0435 \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0434\u043e \u0432\u0441\u0435\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044e         def num_reachable_neighbors(city):             # \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043a\u0443\u0447\u0443, \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0441 \u043f\u0430\u0440\u043e\u0439, \u0437\u0430\u0434\u0430\u044e\u0449\u0435\u0439 \u043d\u0443\u043b\u0435\u0432\u0443\u044e              # \u0434\u043b\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 \u0434\u043e \u0441\u0430\u043c\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0433\u043e\u0440\u043e\u0434\u0430             heap = [(0, city)]             # \u0438 \u043c\u0430\u0441\u0441\u0438\u0432, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0433\u043e\u0440\u043e\u0434\u0430 \u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435              # \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e \u043d\u0438\u0445 \u043e\u0442 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e             distances = {}             # \u0437\u0430\u0442\u0435\u043c, \u043f\u043e\u043a\u0430 \u043a\u0443\u0447\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430, \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0439              # \u043e\u0442 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 \u0433\u043e\u0440\u043e\u0434             while heap:                 currDist, neighb = heapq.heappop(heap)                 # \u0435\u0441\u043b\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0435 \u0440\u0435\u0431\u0440\u043e \u0432\u0435\u0434\u0435\u0442 \u043a \u0433\u043e\u0440\u043e\u0434\u0443, \u0433\u0434\u0435 \u043c\u044b \u0443\u0436\u0435 \u0437\u043d\u0430\u0435\u043c                  # \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442, \u0442\u043e \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e                 if neighb in distances:                     continue                 # \u0432 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u0438 \u0435\u0441\u043b\u0438 \u0441\u043e\u0441\u0435\u0434 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0442\u043f\u0440\u0430\u0432\u043d\u044b\u043c                  # \u0433\u043e\u0440\u043e\u0434\u043e\u043c, \u043c\u044b \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043d\u043e\u0432\u0443\u044e \u0437\u0430\u043f\u0438\u0441\u044c \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439                 if neighb != city:                         distances[neighb] = currDist                 # \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0432\u0441\u0435\u0445 \u0441\u043c\u0435\u0436\u043d\u044b\u0445 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 \u0441 \u0441\u043e\u0441\u0435\u0434\u043e\u043c, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044f \u0438\u0445 \u0432 \u043a\u0443\u0447\u0443                  # \u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u043b\u0438: \u0430) \u0434\u043e \u043d\u0438\u0445 \u0435\u0449\u0435 \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u0438 \u0431) \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u0438\u0445 \u0447\u0435\u0440\u0435\u0437 neighb \u043d\u0435 \u0432\u044b\u0445\u043e\u0434\u0438\u0442 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b mileage                 for node, d in graph[neighb]:                     if node in distances:                         continue                     if currDist + d &lt;= mileage:                         heapq.heappush(heap, (currDist + d, node))             # \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0433\u043e\u0440\u043e\u0434\u043e\u0432, \u043f\u0440\u043e\u0448\u0435\u0434\u0448\u0438\u0445 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443             return len(distances)                  # \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043c \u043f\u043e\u0438\u0441\u043a \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0433\u043e\u0440\u043e\u0434\u043e\u0432         cities_neighbors = {num_reachable_neighbors(city): city for city in range(n)}         # \u0432\u0435\u0440\u043d\u0451\u043c \u043d\u043e\u043c\u0435\u0440 \u0433\u043e\u0440\u043e\u0434\u0430, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439         # \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u0434\u043e\u0441\u0438\u0433\u0430\u0435\u043c\u043e\u0441\u0442\u0438         return cities_neighbors[min(cities_neighbors)] <\/code><\/pre>\n<p>  \u0412 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432\u044b\u0448\u0435, \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445, \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043a\u0430\u043a \u043c\u0435\u0442\u043e\u0434 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u043a\u0443\u0447\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u0439\u0442\u0438 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043e \u0432\u0441\u0435\u0445 \u0433\u043e\u0440\u043e\u0434\u043e\u0432, \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 `mileage`. \u041e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0432\u0430\u043b\u044f\u0435\u0442 \u0446\u0438\u043a\u043b, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u0441 \u043a\u0443\u0447\u0435\u0439.<\/p>\n<h3>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h3>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u044d\u0442\u043e \u043c\u043e\u0449\u043d\u044b\u0439 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442 \u0432 \u043c\u0438\u0440\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438, \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0435\u0433\u043e \u043a\u0440\u0430\u0439\u043d\u0435 \u0448\u0438\u0440\u043e\u043a\u0430. \u0421 \u0435\u0433\u043e \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043c\u043e\u0436\u043d\u043e \u043e\u0446\u0435\u043d\u0438\u0442\u044c \u0434\u0430\u0436\u0435 \u0446\u0435\u043b\u0435\u0441\u043e\u043e\u0431\u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u043e\u0439 \u0432\u0435\u0442\u043a\u0438 \u043c\u0435\u0442\u0440\u043e, \u043d\u043e\u0432\u043e\u0439 \u0434\u043e\u0440\u043e\u0433\u0438 \u0438\u043b\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0432 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043d\u043e\u0439 \u0441\u0435\u0442\u0438. \u041e\u043d \u043f\u0440\u043e\u0441\u0442 \u0432 \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0438 \u0438 \u0438\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u0435\u043d, \u043a\u0430\u043a \u0434\u0440\u0443\u0433\u0438\u0435 \u0436\u0430\u0434\u043d\u044b\u0435 (greedy) \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u0412\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0437\u0430\u0434\u0430\u0447 \u0441 \u0435\u0433\u043e \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u043d\u0435 \u0432\u044b\u0448\u0435 $$\\inline O(m \\ log(n)). \u041f\u0440\u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u043c\u043e\u0436\u0435\u0442 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 (\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438, \u0440\u0435\u0448\u0430\u044e\u0449\u0438\u0439 \u043f\u0435\u0440\u0432\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u043f\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0438, \u0447\u0442\u043e \u0433\u0440\u0430\u0444 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439).<\/p>\n<p>  <\/p>\n<p>\u0421\u0442\u043e\u0438\u0442 \u0435\u0449\u0435 \u0440\u0430\u0437 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u043a\u043e\u0433\u0434\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u2014 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430 \u2013 \u0424\u043e\u0440\u0434\u0430, \u0447\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0441\u043b\u0443\u0436\u0438\u0442\u044c \u0442\u0435\u043c\u043e\u0439 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438. \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u044d\u0442\u043e, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u0435\u043b\u0435\u043c \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0431\u0430\u043b\u0430\u043d\u0441\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0438 \u043c\u043e\u0449\u0438, \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447.<\/p>\n<blockquote><p>\u0421\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d\u0430 \u0432 \u043f\u0440\u0435\u0434\u0434\u0432\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u043a\u0443\u0440\u0441\u0430 <a href=\"https:\/\/otus.pw\/OW4o\/\">\u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u043e\u0432\u00bb<\/a>. \u0423\u0437\u043d\u0430\u0442\u044c \u043e \u043a\u0443\u0440\u0441\u0435 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0437\u0430\u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0431\u0435\u0441\u043f\u043b\u0430\u0442\u043d\u044b\u0439 \u0434\u0435\u043c\u043e\u0443\u0440\u043e\u043a <a href=\"https:\/\/otus.pw\/OW4o\/\">\u043c\u043e\u0436\u043d\u043e \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435<\/a>.<\/p><\/blockquote>\n<h3>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h3>\n<p>  [1] \u0423\u0441\u043b\u043e\u0432\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u0432\u0437\u044f\u0442\u044b \u0438\u0437 \u043a\u043d\u0438\u0433\u0438 \u00abAlgorithms Illuminated: Part 2: Graph Algorithms and Data Structures\u00bb \u043e\u0442 Tim Roughgarden,<br \/>  [2] \u0438 \u0441 \u0441\u0430\u0439\u0442\u0430 leetcode.com.<br \/>  [3] \u0420\u0435\u0448\u0435\u043d\u0438\u044f \u0430\u0432\u0442\u043e\u0440\u0441\u043a\u0438\u0435.<\/div>\n<\/div>\n<\/div>\n<div class=\"v-portal\" style=\"display:none;\"><\/div>\n<\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/599621\/\"> https:\/\/habr.com\/ru\/company\/otus\/blog\/599621\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><img decoding=\"async\" src=\"\/img\/image-loader.svg\" data-src=\"https:\/\/habrastorage.org\/webt\/nz\/pb\/w3\/nzpbw391_h_aqdzjdygc_n0tcfk.png\"\/><\/p>\n<p>  \u041f\u043e\u0438\u0441\u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435. \u0422\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0447\u0430\u0441\u0442\u043e \u0438 \u0432 \u043f\u043e\u0432\u0441\u0435\u0434\u043d\u0435\u0432\u043d\u043e\u0439 \u0436\u0438\u0437\u043d\u0438, \u0438 \u0432 \u043c\u0438\u0440\u0435 \u0442\u0435\u0445\u043d\u043e\u043b\u043e\u0433\u0438\u0439. \u0421\u043f\u0440\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u0441 \u0442\u0430\u043a\u0438\u043c\u0438 \u0432\u044b\u0437\u043e\u0432\u0430\u043c\u0438 \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0432 \u0430\u0440\u0441\u0435\u043d\u0430\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u0430 \u2014 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. <\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u043d\u0430\u0439\u0442\u0438 \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441\u044b, \u0447\u0435\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043b\u0443\u0447\u0448\u0435 BFS (\u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443), \u043f\u0440\u0438 \u043a\u0430\u043a\u0438\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c, \u0438 \u043a\u0430\u043a\u0438\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0438 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u043d\u043e \u0441 \u0435\u0433\u043e \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0440\u0435\u0448\u0430\u0442\u044c, \u0447\u0438\u0442\u0430\u0439\u0442\u0435 \u0434\u0430\u043b\u0435\u0435.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-328501","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/328501","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=328501"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/328501\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=328501"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=328501"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=328501"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}