{"id":374930,"date":"2024-05-21T06:12:23","date_gmt":"2024-05-21T06:12:23","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=374930"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=374930","title":{"rendered":"\u041f\u043e\u0445\u043e\u0436\u0435, \u044f \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b \u0441\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 (upd: \u043c\u0435\u043d\u044f \u043e\u043f\u0435\u0440\u0435\u0434\u0438\u043b\u0438…)<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

\u0412\u0441\u0435\u043c \u043f\u0440\u0438\u0432\u0435\u0442! \u042f \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043b, \u043f\u043e\u0445\u043e\u0436\u0435, \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0440\u0435\u0431\u0440\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430.<\/p>\n

\u041f\u043e\u0447\u0435\u043c\u0443 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439? \u042f \u0438\u0441\u043a\u0430\u043b \u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u043d\u0435 \u043d\u0430\u0448\u0435\u043b, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043e\u043d\u043e \u0443\u0436\u0435 \u0431\u044b\u043b\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e, \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043b\u043e\u0445\u043e \u043f\u043e\u0438\u0441\u043a\u0430\u043b. \u0416\u0434\u0443 \u041d\u043e\u0431\u0435\u043b\u0435\u0432\u0441\u043a\u0443\u044e \u043f\u0440\u0435\u043c\u0438\u044e =)<\/p>\n

\u0414\u043e\u0434\u0443\u043c\u0430\u043b\u0441\u044f \u044f \u0434\u043e \u043d\u0435\u0433\u043e \u043f\u0443\u0442\u0435\u043c \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. \u041f\u0440\u043e\u0448\u0443 \u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u043e \u043e\u0442\u043d\u0435\u0441\u0442\u0438\u0441\u044c \u043a \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u043c\u0443, \u0438\u0431\u043e \u044d\u0442\u043e \u043c\u043e\u044f \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f, \u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044f \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u044b\u0432\u0430\u043b \u0438, \u0432\u043e\u043e\u0431\u0449\u0435, \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432\u043e\u0432\u0441\u0435 (\u043d\u043e \u043f\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c \u0442\u0435\u0441\u0442\u0430\u043c \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e).<\/p>\n

\u041f\u043e\u0432\u0442\u043e\u0440\u044e\u0441\u044c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0440\u0435\u0431\u0440\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430<\/strong> (\u043d\u043e \u043d\u0435 \u0441 \u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438). \u0427\u0435\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430?<\/p>\n

\u042d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e! \u0423 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 O(En), \u0433\u0434\u0435 n — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432, \u0415 — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0431\u0435\u0440. \u0423 «\u043c\u043e\u0435\u0433\u043e» \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0442\u0430\u043a\u0430\u044f \u0436\u0435 \u0430\u0441\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c. \u041d\u043e \u043f\u043e \u043c\u043e\u0438\u043c \u0440\u0430\u0441\u0447\u0435\u0442\u0430\u043c \u0445\u0443\u0434\u0448\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f. \u0410 \u0443 \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430 \u0445\u0443\u0434\u0448\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435 (\u043e\u0431 \u044d\u0442\u043e\u043c \u0434\u0430\u043b\u0435\u0435). \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e O(n2<\/sup>+E). \u041e\u0431 \u044d\u0442\u043e\u043c \u0442\u043e\u0436\u0435 \u043d\u0430\u043f\u0438\u0448\u0443 \u0434\u0430\u043b\u0435\u0435. \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Python:<\/em><\/strong><\/p>\n

P.S.<\/h4>\n

\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u044b \u043c\u043d\u043e\u0433\u0438\u0435 \u043c\u043e\u043c\u0435\u043d\u0442\u044b, \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0443 \u0437\u0430 \u0442\u0435\u0441\u0442-\u043a\u0435\u0439\u0441\u044b \u0438 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043a\u0438. \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438 \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u044b\u043c\u0438 (\u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0441\u0430\u0440\u043a\u0430\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438-\u043e\u0441\u043a\u043e\u0440\u0431\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435), \u0442.\u043a. \u044f \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u043b \u0440\u0430\u0431\u043e\u0442\u043e\u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n

\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n
\"\u041f\u0440\u0438\u043c\u0435\u0440<\/p>\n
\u041f\u0440\u0438\u043c\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c<\/figcaption><\/div>\n<\/figure>\n

\u0418\u0442\u0430\u043a, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0433\u0440\u0430\u0444 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c \u043c\u0435\u0436\u0434\u0443 2-\u043c \u0438 5-\u043c \u0443\u0437\u043b\u043e\u043c. \u041d\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 — \u043d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 (1-\u0433\u043e \u0443\u0437\u043b\u0430) \u0434\u043e 9-\u0433\u043e \u0443\u0437\u043b\u0430 (\u043b\u0438\u0431\u043e \u0434\u043e \u043b\u044e\u0431\u043e\u0433\u043e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u043e\u0433\u043e).<\/p>\n

\u0413\u0440\u0430\u0444 \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0432 \u0432\u0438\u0434\u0435 \u0445\u044d\u0448 \u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u0433\u0434\u0435:<\/p>\n

graph = {
\u043d\u043e\u0434\u0430_1_(\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a): {\u0441\u043e\u0441\u0435\u0434_1: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, \u0441\u043e\u0441\u0435\u0434_2: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, …},
\u043d\u043e\u0434\u0430_2: {\u0441\u043e\u0441\u0435\u0434_1: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, \u0441\u043e\u0441\u0435\u0434_2: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, …},
…
}<\/em><\/p>\n

graph = {     1: {2: 10, 3: 6, 4: 8},     2: {7: 11, 4: 5, 5: -4},     3: {5: 3},     4: {7: 12, 3: 2, 5: 5, 6: 7},     5: {6: 9, 9: 12},     6: {8: 8, 9: 10},     7: {6: 4, 8: 6, 9: 16},     8: {9: 15},     9: {} }<\/code><\/pre>\n
\u0412\u0430\u0436\u043d\u043e! <\/strong>\u041d\u0443\u0436\u043d\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u0433\u0440\u0430\u0444\u0430 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0438\u0445 \u043e\u0442\u0434\u0430\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u0422.\u0435. \u0441\u043f\u0435\u0440\u0432\u0430 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043e\u043f\u0438\u0441\u0430\u043b\u0438 \u0438\u0445, \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0430\u0435\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0441\u043e\u0441\u0435\u0434\u044f\u043c \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0422.\u0435. \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043f\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e, \u0431\u0443\u0434\u0442\u043e \u044d\u0442\u043e \u043d\u0435 \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u0430 \u043e\u0431\u044b\u043a\u043d\u043e\u0432\u0435\u043d\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0433\u0434\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0435\u043c \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. \u0412 Python \u0441\u043b\u043e\u0432\u0430\u0440\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u043c\u0438 (\u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0432\u0435\u0440\u0441\u0438\u0438 3.6), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u043c \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u0438\u0431\u0435\u0433\u0430\u0442\u044c \u043a \u0434\u0440\u0443\u0433\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430\u043c \u0434\u0430\u043d\u043d\u044b\u0445, \u0442\u0438\u043f\u0430 Ordered dict<\/em> \u0438\u0437 \u043c\u043e\u0434\u0443\u043b\u044f collections<\/em>.
\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u0433\u0440\u0430\u0444 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0435\u0439, \u043d\u043e \u043c\u043d\u0435 \u0442\u0430\u043a \u043f\u0440\u043e\u0449\u0435.<\/p>\n\n
P.S. \u0422\u043e\u0442, \u043a\u0442\u043e \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c:<\/strong><\/p>\n
\n
\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u0437\u043d\u0430\u0435\u0442\u0435? \u041d\u0430\u0431\u043e\u0440 \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0434\u0443\u0433, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u0443\u0433\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0430\u0440\u0430\u043c\u0438 \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u043f\u043b\u044e\u0441\u043e\u043c \u0432\u0435\u0441\u0430 \u0434\u043b\u044f \u0434\u0443\u0433 \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0438. \u041d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0442\u0430\u043c \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u043d\u0435 \u043f\u0440\u0435\u0434\u0443\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043e.<\/p>\n<\/blockquote>\n
\u0417\u0430\u0440\u0430\u043d\u0435\u0435 \u043e\u0442\u0432\u0435\u0447\u0430\u044e.<\/p>\n
\u0425\u043e\u0440\u043e\u0448\u043e, \u0431\u0443\u0434\u0443 \u043e\u0442 \u0432\u0430\u0448\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043e\u0442\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u0442\u044c\u0441\u044f. \u0423 \u043d\u0430\u0441 \u043a\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430? \u041d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 \u0410 \u0432 \u0442\u043e\u0447\u043a\u0443 \u0412. \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0432 \u0432\u0430\u0448\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0433\u0440\u0430\u0444\u0430 \u0442\u043e\u0447\u043a\u0443 \u0410 \u0438 \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u041f\u043e\u0442\u043e\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u044d\u0442\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u0442.\u0434. \u0412\u043e\u0442 \u044d\u0442\u043e «\u043d\u0430\u0445\u043e\u0434\u0438\u043c» \u0432 \u0432\u0430\u0448\u0435\u0439 \u0431\u0435\u0441\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430 N \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f N \u0440\u0430\u0437. \u042d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u044b \u0443 \u0432\u0430\u0441 \u043f\u0440\u043e\u0441\u0442\u043e \u0431\u0435\u0441\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u043d\u043e \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u044b \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 (\u0435\u0441\u043b\u0438 \u0432\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0435 \u044d\u0442\u0443 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f). \u041e\u0431\u044b\u0447\u043d\u043e \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0434\u044b \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c \u044f\u0447\u0435\u0439\u043a\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 \u0434\u043e\u0441\u0442\u0443\u043f \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443. \u0412 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b (\u043d\u0435 \u044f \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b \u0435\u0433\u043e) \u043a\u0430\u043a \u0440\u0430\u0437 \u0442\u0430\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u0438\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0433\u0440\u0430\u0444\u0430, \u0433\u0434\u0435 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0434\u044b (\u0438\u043b\u0438 \u0431\u0443\u043a\u0432\u0430 \u0432 \u043b\u0435\u043a\u0441\u0438\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435) \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c \u044f\u0447\u0435\u0439\u043a\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435. \u0422\u043e, \u043a\u0430\u043a \u0432\u044b \u043f\u044b\u0442\u0430\u0435\u0442\u0435\u0441\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0433\u0440\u0430\u0444 — \u044d\u0442\u043e \u043f\u043e \u0441\u0443\u0442\u0438 \u0432\u044b\u0441\u0442\u0440\u0435\u043b \u0441\u0435\u0431\u0435 \u0432 \u043d\u043e\u0433\u0443. \u0415\u0441\u043b\u0438 \u043e\u0442\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0439 \u0436\u0438\u0437\u043d\u0438, \u043d\u0443\u0436\u043d\u043e \u0435\u0449\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0433\u0440\u0430\u0444\u0430. \u0423\u0441\u043b\u043e\u0432\u043d\u043e \u0442\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u0448\u044c\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043a\u0435 1, \u043c\u043d\u0435 \u043d\u0430\u0434\u043e \u0432 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043e\u043a 10. \u0410 \u0434\u0430\u0439 \u043a\u0430 \u0433\u043b\u044f\u043d\u0443, \u043a\u0430\u043a\u0438\u0435 \u0442\u0430\u043c \u0434\u043e\u0440\u043e\u0433\u0438 \u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0438\u0437 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043a\u0430 7 \u0438 \u0437\u0430\u043f\u0438\u0448\u0443. \u0425\u043e\u0442\u044f \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0434\u043e\u0440\u043e\u0433\u0438 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043a\u0430 2. \u0412 \u043e\u0431\u0449\u0435\u043c, \u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u0435 \u0432\u0430\u0448\u0435 \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043d\u043e \u044d\u0442\u043e \u0432\u0441\u0451 \u043e\u0431\u0449\u0435\u043f\u0440\u0438\u043d\u044f\u0442\u0430\u044f \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u0430, \u044f \u044d\u0442\u043e \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u044b\u0432\u0430\u043b.<\/em> 
\u041f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0436\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u0441\u044f \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u043d\u0438\u043a\u0430\u043a \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/strong><\/p>\n
\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0435\u0441\u043b\u0438 \u0434\u0430\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0430, \u0433\u0434\u0435 \u043d\u0430 \u0432\u0445\u043e\u0434 \u043f\u043e\u0434\u0430\u0435\u0442\u0441\u044f \u0433\u0440\u0430\u0444 \u0432\u0438\u0434\u0430: input_graph = [[\u0443\u0437\u0435\u043b_2, \u0443\u0437\u0435\u043b_5, \u0432\u0435\u0441 \u0434\u043e \u0443\u0437\u043b\u0430_5], [\u0443\u0437\u0435\u043b_7, \u0443\u0437\u0435\u043b_1, \u0432\u0435\u0441 \u0434\u043e \u0443\u0437\u043b\u0430_1] …], \u0447\u0438\u0441\u043b\u043e n — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432, k — \u0443\u0437\u0435\u043b-\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0432\u0441\u0435\u0445 \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0445<\/em> \u0432\u0435\u0440\u0448\u0438\u043d (\u043e\u0431\u044b\u0447\u043d\u043e \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b, \u043d\u043e \u0435\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u044d\u0442\u043e\u0439 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0438 \u043d\u0435\u0442, \u0442\u043e \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442, \u044d\u0442\u0443 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u044f \u0442\u0430\u043a \u0436\u0435 \u043f\u043e\u043a\u0430\u0436\u0443). \u041a\u043e\u0434 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043c\u043e\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0431\u0443\u0434\u0435\u0442 \u0442\u0430\u043a\u043e\u0439:<\/p>\n
from collections import deque  input_graph = [[1, 2, 10], [2, 1, 10], [3, 2, 1]]  n = int(input())  # 3 k = int(input())  # 1  arr = [[] for _ in range(n + 1)] graph = {}  for item in input_graph:     arr[item[0]].append((item[1], item[2]))  queue = deque() graph[k] = {} for i in arr[k]:     neighbor = i[0]     graph[k][neighbor] = i[1]     queue.append(neighbor)  while queue:     current = queue.popleft()     if current not in graph:         graph[current] = {}     for i in arr[current]:         neighbor = i[0]         if neighbor not in graph:             graph[i[0]] = {}             queue.append(neighbor)          graph[current][neighbor] = i[1]  # -> graph = {1: {2: 10}, 2: {1: 10}} # 3-\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u0442.\u043a. \u043e\u043d\u0430 \u043d\u0435\u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u0430 \u0441 1-\u043e\u0439 \u043d\u043e\u0434\u044b! # \u0415\u0441\u043b\u0438 \u0431\u044b k=3, \u0442\u043e\u0433\u0434\u0430: # graph = {3: {2: 1}, 2: {1: 10}, 1: {2: 10}}}<\/code><\/pre>\n
\u0421 \u044d\u0442\u0438\u043c \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u0438\u0434\u0435\u043c \u0434\u0430\u043b\u044c\u0448\u0435.<\/p>\n\n
\u0422\u0430\u043a \u0436\u0435 \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0435\u0449\u0435 2 \u0445\u044d\u0448 \u0442\u0430\u0431\u043b\u0438\u0446\u044b.
 \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b \u0432 \u0432\u0438\u0434\u0435:
 costs = {
 \u043d\u043e\u0434\u0430_1_(\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a): 0,
 \u043d\u043e\u0434\u0430_2: infinity,
 \u043d\u043e\u0434\u0430_3: infinity,
 …
 }
\u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043c\u044b \u0435\u0435 \u0431\u0443\u0434\u0435\u043c \u043f\u043e \u043c\u0435\u0440\u0435 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u043e «\u0434\u0435\u0442\u044f\u043c» \u0443\u0437\u043b\u043e\u0432.<\/p>\n
costs = {}  # \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 (\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0434\u043b\u0438\u043d\u044b \u043f\u0443\u0442\u0438 \u0434\u043e \u043d\u043e\u0434\u044b \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430)<\/code><\/pre>\n
\u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u043d\u043e\u0434, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b:<\/p>\n
parents = {}  # {\u041d\u043e\u0434\u0430: \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c}<\/code><\/pre>\n
\u0415\u0435 \u0442\u0430\u043a \u0436\u0435 \u0431\u0443\u0434\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043f\u043e \u043c\u0435\u0440\u0435 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u043e \u0434\u0435\u0442\u044f\u043c \u0443\u0437\u043b\u043e\u0432.<\/p>\n
\u041a\u0430\u043a \u0438 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0431\u0443\u0434\u0435\u043c \u043e\u0442\u043c\u0435\u0447\u0430\u0442\u044c \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0434\u043e \u0443\u0437\u043b\u043e\u0432 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c\u044e. \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u044d\u0442\u0443 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e:<\/p>\n
infinity = float('inf')  # \u0411\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c (\u043a\u043e\u0433\u0434\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043e \u043d\u043e\u0434\u044b \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d)<\/code><\/pre>\n
\u0414\u0430\u043b\u0435\u0435 \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043f\u0443\u0441\u0442\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e. \u0422\u0430\u043c \u0431\u0443\u0434\u0443\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b (\u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442 «\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435», \u043f\u043e\u044f\u0441\u043d\u044e \u0434\u0430\u043b\u0435\u0435, \u0430 \u043f\u043e\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e)<\/p>\n
processed = set()  # \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043d\u043e\u0434<\/code><\/pre>\n
\u0412\u0432\u0435\u0434\u0435\u043c \u043d\u043e\u0432\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 — \u0441\u043f\u0438\u0441\u043e\u043a \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430.<\/p>\n
lst = deque([key for key in graph.keys()])  # \u0424\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430<\/code><\/pre>\n
\u041f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c \u043a \u0441\u0430\u043c\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443!<\/strong><\/p>\n
    \n
  1. \n
    \u041d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 (\u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430). \u0421\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0432\u0435\u0441\u0430 \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 costs<\/em>. \u041f\u0443\u0442\u044c \u0434\u043e \u043d\u0438\u0445 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439, \u0430 \u043b\u044e\u0431\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0443\u0436\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c \u0432\u0435\u0441\u0430. \u0422\u0430\u043a \u0436\u0435 \u0432\u043d\u043e\u0441\u0438\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u0432\u0441\u0435\u0445 \u0443\u0437\u043b\u043e\u0432, \u0442.\u043a. \u043c\u044b \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b\u0438 \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u043e\u0434\u044b  \u043a\u043e\u0440\u043e\u0447\u0435. \u041a\u043e\u0433\u0434\u0430 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0432\u043d\u043e\u0441\u0438\u043c \u043d\u0430\u0448 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 processed<\/em> (\u044d\u0442\u043e\u0442 \u0443\u0437\u0435\u043b \u043c\u044b \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c).<\/p>\n<\/li>\n
  2. \n
    \u0417\u0434\u0435\u0441\u044c \u0432\u0430\u0436\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0438 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e \u0432\u0435\u0441\u0443<\/em> \u043d\u0435\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b, \u0430 \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u043e\u0431\u0449\u0435 \u0412\u0421\u0415\u0425<\/strong> \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u043e\u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e. \u0422.\u0435. \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0438 \u043f\u043e\u0441\u043b\u0435 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u044d\u0442\u0430\u043f\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.
     \u041c\u044b \u043f\u043e\u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e \u0442\u0430\u043a \u0436\u0435 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u0443\u0436\u0435 \u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0432\u043d\u0435\u0441\u0435\u043d\u043d\u044b\u0439 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443, \u0442\u043e \u043c\u044b \u0435\u0433\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c. \u0422\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 parents<\/em>.
    \u041a\u043e\u0433\u0434\u0430 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0432\u043d\u043e\u0441\u0438\u043c \u0443\u0437\u0435\u043b \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445. \u0422.\u0435. \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445<\/strong> — \u044d\u0442\u043e \u0442\u0435 \u0443\u0437\u043b\u044b, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439!<\/p>\n<\/li>\n
  3. \n
    \u0418 \u0442\u0430\u043a \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u043f\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e (\u043d\u0435 \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0430\u0435\u043c \u043a \u0441\u043e\u0441\u0435\u0434\u044f\u043c \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439), \u043f\u043e\u043a\u0430 \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b \u0432\u0441\u0435 \u0443\u0437\u043b\u044b.<\/p>\n<\/li>\n
  4. \n
    \u0421\u043f\u0438\u0441\u043e\u043a \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0443\u0436\u0438\u0442\u044c \u043d\u0430\u0448\u0435\u0439 \u0438\u0442\u0435\u0440\u0430\u0431\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430. \u0417\u0430\u0447\u0435\u043c? \u0415\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u0443 \u043d\u043e\u0434\u044b \u0441\u043e\u0441\u0435\u0434\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0443\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u0430\u044f \u043d\u043e\u0434\u0430, \u0442\u043e \u043c\u044b \u044d\u0442\u0443 \u043d\u043e\u0434\u0443 \u0441\u043d\u043e\u0432\u0430 \u0431\u0443\u0434\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c, \u0442.\u043a. \u0432\u0435\u0441\u0430 \u0434\u0435\u0442\u0435\u0439 \u043c\u043e\u0433\u0443\u0442 \u0441\u0442\u0430\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435.<\/p>\n
    \u041a\u043e\u0434:<\/p>\n<\/li>\n<\/ol>\n
    from collections import deque  graph = {     1: {2: 10, 3: 6, 4: 8},     2: {7: 11, 4: 5, 5: -4},     3: {5: 3},     4: {7: 12, 3: 2, 5: 5, 6: 7},     5: {6: 9, 9: 12},     6: {8: 8, 9: 10},     7: {6: 4, 8: 6, 9: 16},     8: {9: 15},     9: {} }  lst = deque([key for key in graph.keys()])  # \u0424\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430 parents = {}  # {\u041d\u043e\u0434\u0430: \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c} costs = {}  # \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 (\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0434\u043b\u0438\u043d\u044b \u043f\u0443\u0442\u0438 \u0434\u043e \u043d\u043e\u0434\u044b \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430) infinity = float('inf')  # \u0411\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c (\u043a\u043e\u0433\u0434\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043e \u043d\u043e\u0434\u044b \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d) processed = set()  # \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043d\u043e\u0434  while lst:     node = lst.popleft()     if node not in processed:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0443\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0435\u0435 \u0437\u0430\u043d\u043e\u0432\u043e \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c (\u0438\u043d\u0430\u0447\u0435 \u043c.\u0431. \u0431\u0435\u0441\u043a. \u0446\u0438\u043a\u043b)         for child, cost in graph[node].items():  # \u041f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0434\u0435\u0442\u044f\u043c             new_cost = cost + costs.get(node,                                         0)  # \u041f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 = \u043f\u0443\u0442\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f + \u0432\u0435\u0441 \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043d\u0435\u0442, \u0442\u043e \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u0435\u0433\u043e = 0)             min_cost = costs.get(child,                                  infinity)  # \u0421\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0435\u0433\u043e \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0431\u044b\u043b\u043e, \u0442\u043e \u043e\u043d \u0431\u0435\u0441\u043a.)             if new_cost < min_cost:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e \u044d\u0442\u043e\u0433\u043e,                 costs[child] = new_cost  # \u0442\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439                 parents[child] = node  # \u0422\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u0438\u043d \u043f\u0443\u0442\u044c                 if child in processed:  # \u0415\u0441\u043b\u0438 \u0440\u0435\u0431\u0435\u043d\u043e\u043a \u0431\u044b\u043b \u0432 \u0447\u0438\u0441\u043b\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445                     lst.appendleft(child)  # \u0412\u043d\u043e\u0432\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u0442\u0443 \u043d\u043e\u0434\u0443 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0435\u0433\u043e \u0437\u0430\u043d\u043e\u0432\u043e                     processed.remove(child)  # \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0438\u0437 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445         processed.add(node)  # \u041a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u0434\u0435\u0442\u0438 (\u0440\u0435\u0431\u0440\u0430 \u0433\u0440\u0430\u0444\u0430) \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b, \u0432\u043d\u043e\u0441\u0438\u043c \u043d\u043e\u0434\u0443 \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445  print(f'\u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u043d\u043e\u0434\u044b: {costs}') print(f'\u0420\u043e\u0434\u0438\u0442\u0435\u043b\u0438 \u043d\u043e\u0434, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b: {parents}')  # -> \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u043d\u043e\u0434\u044b: {2: 10, 3: 6, 4: 8, 7: 20, 5: 6, 6: 15, 9: 18, 8: 23} # -> \u0420\u043e\u0434\u0438\u0442\u0435\u043b\u0438 \u043d\u043e\u0434, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b: {2: 1, 3: 1, 4: 1, 7: 4, 5: 2, 6: 4, 9: 5, 8: 6}<\/code><\/pre>\n
    \u041c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435, \u0430 \u0442\u0430\u043a \u0436\u0435 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u044d\u0442\u0438\u0445 \u0443\u0437\u043b\u043e\u0432. \u041a\u0430\u043a \u0436\u0435 \u043d\u0430\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0446\u0435\u043f\u043e\u0447\u043a\u0443 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0435\u0433\u043e \u043d\u0430\u0441 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e 9-\u043e\u0439 \u043d\u043e\u0434\u044b (\u043b\u0438\u0431\u043e \u0434\u043e \u043b\u044e\u0431\u043e\u0439 \u0434\u0440\u0443\u0433\u043e\u0439 \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u043e\u0439)? \u041e\u0442\u0432\u0435\u0442 \u0432 \u043a\u043e\u0434\u0435 \u043d\u0438\u0436\u0435:<\/p>\n
    def get_shortest_path(start, end):     '''     \u041f\u0440\u043e\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f\u043c, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438,     \u0442.\u0435. \u0438\u0449\u0435\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438, \u043f\u043e\u0442\u043e\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0438 \u0442.\u0434. \u043f\u043e\u043a\u0430 \u043d\u0435 \u0434\u043e\u0439\u0434\u0435\u0442 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0443\u0442\u0438.     \u0422\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u0443\u044e \u0446\u0435\u043f\u043e\u0447\u043a\u0443 \u043d\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u044b \u0438\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432 \u043a\u043e\u043d\u0446\u0435, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c     \u0438\u0441\u0442\u0438\u043d\u043d\u044b\u0439 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c     '''     parent = parents[end]     result = [end]     while parent != start:         result.append(parent)         parent = parents[parent]     result.append(start)     result.reverse()       result = map(str, result)  # \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0435\u0441\u043b\u0438 \u0438\u043c\u0435\u043d\u0430 \u043d\u043e\u0434 \u0431\u0443\u0434\u0443\u0442 \u0447\u0438\u0441\u043b\u0430\u043c\u0438, \u0430 \u043d\u0435 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 (\u0434\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e join)     shortest_distance = costs[end]     print(f'\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 {start} \u0434\u043e {end}:  {shortest_distance}')     return result   shortest_path = get_shortest_path(start=1, end=9) print('-->'.join(shortest_path))  # -> \u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 1 \u0434\u043e 9:  18 # -> 1-->2-->5-->9<\/code><\/pre>\n
    \u0418\u0442\u0430\u043a, \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e 9 \u0443\u0437\u043b\u0430, \u0438 \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u043e\u043d \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u0447\u0435\u0440\u0435\u0437 \u0440\u0435\u0431\u0440\u043e \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0432\u0435\u0441\u043e\u043c! \u0422.\u0435. \u043d\u0430\u0441 \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0435 \u043f\u0443\u0433\u0430\u0435\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u0435\u0431\u0440\u0430, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. <\/p>\n
    \u0415\u0449\u0435 \u0434\u0435\u0442\u0430\u043b\u044c \u0442\u0430\u043a\u0430\u044f. \u041f\u0440\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u043f\u043e\u0438\u0441\u043a \u041c\u0418\u041d\u0418\u041c\u0410\u041b\u042c\u041d\u041e\u0413\u041e \u043f\u043e \u0432\u0435\u0441\u0443 \u0443\u0437\u043b\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u0442 \u0441 \u043d\u0430\u0448\u0438\u043c \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c \u0446\u0435\u043b\u0435\u0432\u044b\u043c \u0443\u0437\u043b\u043e\u043c,
     \u0442\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u0435\u0440\u0432\u0430\u0442\u044c \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0443\u044e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443, \u0442.\u043a. \u043c\u044b \u0443\u0436\u0435 \u043d\u0430\u0448\u043b\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430. \u0412 «\u043c\u043e\u0435\u043c» \u0436\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u043c\u044b \u0432\u0441\u0435 \u0440\u0430\u0432\u043d\u043e \u0431\u0443\u0434\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u0443\u0437\u043b\u044b.<\/p>\n
    \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/h2>\n
    \u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0442\u043e \u0432 \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0442\u0430\u043a\u0430\u044f \u0436\u0435, \u043a\u0430\u043a \u0443 \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430 — O(N*E). \u041d\u043e \u044f \u0442\u0430\u043a \u0438 \u043d\u0435 \u043d\u0430\u0448\u0435\u043b \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439. \u0412\u043e \u0432\u0441\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b, \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0430\u0441\u0441\u0443\u0436\u0434\u0430\u0442\u044c.<\/strong><\/p>\n
    \u0421\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u0443\u0435\u043c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e «\u0432 \u043b\u043e\u0431». \u041f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0430 \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0435\u043c \u0433\u0440\u0430\u0444\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043d\u0435 \u043f\u0440\u0438\u0441\u043b\u0430\u043b\u0438, \u0433\u0434\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0447\u0443\u0432\u0441\u0442\u0432\u0443\u0442\u0435 \u0441\u0435\u0431\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0445\u0443\u0436\u0435, \u0447\u0435\u043c \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u0430\u0445. \u041f\u0440\u0438\u043c\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 (\u0438\u0437\u0432\u0438\u043d\u044f\u044e\u0441\u044c \u0437\u0430 \u0440\u0443\u0447\u043d\u043e\u0439 \u0440\u0438\u0441\u0443\u043d\u043e\u043a)<\/p>\n
    <\/figure>\n
    graph = {   1: {3:10, 2:1},     3: {5:10, 4:1 },    2: {3:1},     5: {7:10, 6:1 },    4: {5:1},     7: {9:10, 8:1},    6: {7:1},     9: {},   8: {9:1},  }  cycle_count = 0 processed = set()  # \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043d\u043e\u0434 while lst:     node = lst.popleft()     if node not in processed:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0443\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0435\u0435 \u0437\u0430\u043d\u043e\u0432\u043e \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c (\u0438\u043d\u0430\u0447\u0435 \u043c.\u0431. \u0431\u0435\u0441\u043a. \u0446\u0438\u043a\u043b)         for child, cost in graph[node].items():  # \u041f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0434\u0435\u0442\u044f\u043c             cycle_count += 1             new_cost = cost + costs.get(node,                                         0)  # \u041f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 = \u043f\u0443\u0442\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f + \u0432\u0435\u0441 \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043d\u0435\u0442, \u0442\u043e \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u0435\u0433\u043e = 0)             min_cost = costs.get(child,                                  infinity)  # \u0421\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0435\u0433\u043e \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0431\u044b\u043b\u043e, \u0442\u043e \u043e\u043d \u0431\u0435\u0441\u043a.)             if new_cost < min_cost:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e \u044d\u0442\u043e\u0433\u043e,                 costs[child] = new_cost  # \u0442\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439                 parents[child] = node  # \u0422\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u0438\u043d \u043f\u0443\u0442\u044c                 if child in processed:  # UPDATE: \u0435\u0441\u043b\u0438 \u0440\u0435\u0431\u0435\u043d\u043e\u043a \u0431\u044b\u043b \u0432 \u0447\u0438\u0441\u043b\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445                     lst.appendleft(child)  # \u0412\u043d\u043e\u0432\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u0442\u0443 \u043d\u043e\u0434\u0443 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0435\u0433\u043e \u0437\u0430\u043d\u043e\u0432\u043e                     processed.remove(child)  # \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0438\u0437 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445         processed.add(node)  # \u041a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u0434\u0435\u0442\u0438 (\u0440\u0435\u0431\u0440\u0430 \u0433\u0440\u0430\u0444\u0430) \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b, \u0432\u043d\u043e\u0441\u0438\u043c \u043d\u043e\u0434\u0443 \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445          print(f'\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: {cycle_count}') # -> \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: 19 # \u041f\u043e \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0443-\u0424\u043e\u0440\u0434\u0443 \u0431\u044b\u043b\u043e \u0431\u044b: 9*12=108 \u0441\u0443\u0434\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 (\u0443\u0441\u043b\u043e\u0432\u043d\u043e)<\/code><\/pre>\n
    \u041f\u043e \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0443-\u0424\u043e\u0440\u0434\u0443 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u0441\u0443\u0434\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435, \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0432 5 \u0440\u0430\u0437!<\/p>\n
    \u0412\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u043a\u0430\u0437\u0430\u0442\u044c: «\u0434\u0430 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0433\u0440\u0430\u0444 \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u043f\u0430\u043b\u0441\u044f». \u0427\u0442\u043e-\u0436 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0433\u0440\u0430\u0444, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f 100% \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u0434\u043b\u044f \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430, \u0441\u0443\u0434\u044f \u043f\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0438\u0437 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u0432.<\/p>\n
    \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u0442\u0430\u043a\u043e\u0433\u043e \u0432\u0438\u0434\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0433\u0440\u0430\u0444: 1—>2—>3—>4—>5. \u0413\u0434\u0435 \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438\u043c\u0435\u0435\u0442 \u0432\u0435\u0441 1. \u041f\u043e \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0443-\u0424\u043e\u0440\u0434\u0443 \u043a\u043e\u043b-\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441\u0432\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u043a\u0430\u043a \u0440\u0430\u0437 \u043a \u0435\u0433\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 (\u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0435\u043c\u0443 \u0441\u043b\u0443\u0447\u0430\u044e), \u0430 \u0438\u043c\u0435\u043d\u043d\u043e 5*4=20. \u0412 \u043c\u043e\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435:  <\/p>\n
    graph = {     1: {2:1},     2: {3:1},     3: {4:1},     4: {5:1},     5: {}, } # -> \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: 4<\/code><\/pre>\n
    \u0422.\u0435. \u043f\u043e \u0441\u0443\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043b\u0441\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0437\u0430 O(E).<\/p>\n
    \u0415\u0441\u043b\u0438 \u044f \u0447\u0442\u043e-\u0442\u043e \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u043b, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c, \u0433\u043b\u0443\u043f\u043e\u0441\u0442\u044c \u0441\u043e\u0432\u0435\u0440\u0448\u0438\u043b, \u0447\u0442\u043e \u0432 «\u043b\u043e\u0431» \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043b \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u0442\u043e \u0441 \u0440\u0430\u0434\u043e\u0441\u0442\u044c\u044e \u0432\u044b\u0441\u043b\u0443\u0448\u0430\u044e, \u0432 \u0447\u0435\u043c \u043c\u043e\u0439 «\u043a\u043e\u0441\u044f\u043a». \u041d\u043e \u0432\u0440\u043e\u0434\u0435 \u043a\u0430\u043a \u0432\u0437\u044f\u043b \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u0435 \u0441\u043b\u0443\u0447\u0430\u0438.<\/p>\n
    \u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0442\u043e \u0435\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u043b\u0443\u0447\u0448\u0435. \u041d\u041e! \u0423 \u043d\u0435\u0433\u043e \u0435\u0441\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0438 \u0444\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438\u0435\u0432\u043e\u0439 \u043a\u0443\u0447. \u0412\u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0430\u043a\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u044b\u0439 \u0431\u0443\u0441\u0442 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u041f\u043e\u044d\u0442\u043e\u043c\u0443, \u0435\u0441\u043b\u0438 \u0432 \u0437\u0430\u0434\u0430\u0447\u0435 \u043d\u0435\u0442 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0440\u0435\u0431\u0435\u0440, \u0442\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043d\u0435\u0436\u0435\u043b\u0438 \u043c\u043e\u0439. \u0412\u044b \u0432 \u044d\u0442\u043e\u043c \u0443\u0431\u0435\u0434\u0438\u0442\u0435\u0441\u044c \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0440\u0430\u0437\u0434\u0435\u043b\u0435.<\/p>\n
    \"\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/p>\n
    \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0439 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b<\/figcaption><\/div>\n<\/figure>\n\n
    \u0421\u0442\u0440\u0435\u0441\u0441 \u0442\u0435\u0441\u0442\u044b<\/h2>\n
    \u0418\u0442\u0430\u043a, \u043f\u043e\u0441\u043b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043c\u043d\u0435 \u043f\u0440\u0438\u0441\u043b\u0430\u043b\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 (\u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u043d\u0435\u0435) \u0441 \u043e\u0447\u0435\u043d\u044c \u0438 \u043e\u0447\u0435\u043d\u044c \u043a\u0430\u0432\u0435\u0440\u0437\u043d\u044b\u043c\u0438 \u0442\u0435\u0441\u0442\u0430\u043c\u0438. <\/p>\n
    \"\u0423\u0441\u043b\u043e\u0432\u0438\u0435<\/p>\n
    \u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/figcaption><\/div>\n<\/figure>\n
    \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435! \u0412 \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0443\u0437\u043b\u044b, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0431\u0435\u0440 \u0441 \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u0432\u0435\u0441\u0430\u043c\u0438 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u044b  \u043d\u0430 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0443\u0437\u0435\u043b. \u0412\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u044d\u0442\u043e \u0432\u043e\u0442 \u0442\u0430\u043a:<\/p>\n
    <\/figure>\n
    \u042d\u0442\u043e \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0433\u0440\u0430\u0444. \u041d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u043d — \u043c\u0443\u043b\u044c\u0442\u0438\u0433\u0440\u0430\u0444. <\/em>\u0421 \u0442\u0430\u043a\u0438\u043c \u0433\u0440\u0430\u0444\u043e\u043c \u043d\u0435 \u0441\u043f\u0440\u0430\u0432\u0438\u0442\u0441\u044f \u043c\u043e\u0439 \u0434\u0435\u0444\u043e\u043b\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0441\u043b\u0443\u0447\u0430\u0438, \u0447\u0442\u043e \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u0442 \u043a \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0440\u0435\u0441\u0443\u0440\u0441\u043d\u044b\u043c \u0440\u0430\u0441\u0445\u043e\u0434\u0430\u043c. \u041d\u043e \u0441\u0440\u0430\u0437\u0443 \u0441\u043a\u0430\u0436\u0443, \u0447\u0442\u043e \u044d\u0442\u0438 \u0440\u0430\u0441\u0445\u043e\u0434\u044b \u0431\u0443\u0434\u0443\u0442 «\u0434\u0435\u0448\u0435\u0432\u043b\u0435», \u0447\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u044d\u0442\u0438\u0445 \u0440\u0435\u0431\u0435\u0440 \u0443 \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432. \u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043b\u0435\u0433\u043a\u0430 \u0443\u0434\u0438\u0432\u0438\u0442\u044c\u0441\u044f:<\/p>\n
    \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432 — 100\u043a
    \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0431\u0435\u0440 — 200\u043a
    \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430 \u0440\u0435\u0431\u0435\u0440 — 1 \u043c\u043b\u0440\u0434<\/em><\/p>\n
    \u041e\u0447\u0435\u043d\u044c \u0434\u0430\u0436\u0435 \u043d\u0435 \u0434\u0443\u0440\u043d\u043e \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. \u0427\u0442\u043e \u0436, \u044f \u0435\u0435 \u0440\u0435\u0448\u0438\u043b \u0441\u0432\u043e\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c! <\/strong>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u0431\u0441\u0443\u0434\u0438\u043c \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u0430\u043c\u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0442\u0430\u043c \u0441\u0430\u043c \u043a\u043e\u0434, \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043e\u0442\u0432\u0435\u0442\u0430. \u042f \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043b \u043c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441  \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043d\u0430 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u043a\u0443\u0447\u0435, \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0424\u043e\u0440\u0434\u043e\u043c-\u0411\u0435\u043b\u043b\u043c\u0430\u043d\u043e\u043c \u0438 \u0441 SPFA. \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u043b \u043d\u0430 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0435 Ryzen 7 5800X. \u0421 \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u0442\u0430\u043c \u0441\u0438\u043b\u044c\u043d\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e!\u00a0\u0421\u0441\u044b\u043b\u043a\u0430<\/a>\u00a0\u043d\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0441 \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c\u0438.  \u0421\u0441\u044b\u043b\u043a\u0430<\/a> \u043d\u0430 \u0441\u0430\u043c\u0443 \u0437\u0430\u0434\u0430\u0447\u0443. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u044f \u0432\u0437\u044f\u043b \u0442\u0435\u0441\u0442\u044b, \u0433\u0434\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u043e\u0441\u0442\u044b\u0435 \u0442\u0435\u0441\u0442\u044b \u044f \u043d\u0435 \u0432\u043a\u043b\u044e\u0447\u0430\u043b \u0432 \u0440\u0430\u0441\u0447\u0435\u0442, \u043e\u043d\u0438 \u0438 \u0442\u0430\u043a \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0442. P.S.<\/strong> \u043d\u0435 \u043f\u044b\u0442\u0430\u0439\u0442\u0435\u0441\u044c \u043f\u0438\u0445\u043d\u0443\u0442\u044c \u043c\u043e\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0432 \u043f\u0440\u043e\u0432\u0435\u0440\u043e\u0447\u043d\u0443\u044e \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u043d\u0430 \u043f\u0438\u0442\u043e\u043d\u0435. \u041a\u043e\u0434 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443 \u043d\u0435 \u043f\u0440\u043e\u0439\u0434\u0435\u0442, \u0442.\u043a. \u0443\u043f\u0440\u0435\u0442\u0441\u044f \u0432 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432 1 \u0441\u0435\u043a. \u0414\u0430\u0436\u0435 \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438\u0437 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043d\u0435 \u0443\u043b\u043e\u0436\u0438\u0442\u0441\u044f \u043a\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0432\u043e \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u0430\u0445 (\u044f \u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b). \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 \u0421++ \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c, \u043d\u043e \u044f \u043d\u0435 \u0437\u043d\u0430\u043a\u043e\u043c \u0441 \u043d\u0438\u043c. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0441\u043c\u043e\u0436\u0435\u0442\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u0434 (\u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u043a\u0443\u0447\u0435) \u0442\u0430\u043a, \u0447\u0442\u043e \u043e\u043d \u0441\u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u043e\u0439\u0442\u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443. \u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0431\u0441\u0443\u0434\u0438\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b.<\/p>\n
    \u0415\u0441\u043b\u0438 \u043a\u0440\u0430\u0442\u043a\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0432\u043e\u0434\u044b, \u0442\u043e \u043c\u044b \u0443\u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430, \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043e\u0447\u0435\u043d\u044c \u043a\u0430\u0432\u0435\u0440\u0437\u043d\u0430\u044f. \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430 100 000 \u0443\u0437\u043b\u0430\u0445 \u0438 200 000 \u0440\u0435\u0431\u0440\u0430\u0445! \u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0435\u0432\u0435\u0441\u0442\u0438 \u0432\u0441\u0435 \u044d\u0442\u043e \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 (\u043f\u0440\u0438\u0447\u0435\u043c \u043d\u0435 \u0441\u0430\u043c\u044b\u0445 \u0434\u0435\u0448\u0435\u0432\u044b\u0445!), \u0442\u043e \u0438\u043c\u0435\u0435\u043c:<\/p>\n
      \n
    1. \n
      \u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0424\u043e\u0440\u0434-\u0411\u0435\u043b\u043b\u043c\u0430\u043d (E*n) \u0437\u0430\u0439\u043c\u0435\u0442 2*10^5 * 10^5 = 20 \u043c\u043b\u0440\u0434 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. SPFA \u0442\u043e \u0436\u0435 \u0441\u0430\u043c\u043e\u0435.<\/p>\n<\/li>\n
    2. \n
      \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u0430 \u0441 \u043a\u0443\u0447\u0435\u0439 (Elogn) \u0437\u0430\u0439\u043c\u0435\u0442 2*10^5 * 17 = 3.4 \u043c\u043b\u043d<\/p>\n<\/li>\n
    3. \n
      \u041c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c (E*n) \u0437\u0430\u0439\u043c\u0435\u0442 2*10^5 * 10^5 = 20 \u043c\u043b\u0440\u0434 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439.<\/p>\n<\/li>\n<\/ol>\n
      \u0412\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438 \u0424\u043e\u0440\u0434-\u0411\u0435\u043b\u043b\u043c\u0430\u043d \u043d\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442.  \u0418 \u0434\u0430\u0436\u0435, \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0442\u0435\u0441\u0442\u0430\u0445 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u0430 \u0441 \u043a\u0443\u0447\u0435\u0439 \u0442\u043e\u0436\u0435 \u043d\u0435 \u0437\u0430\u0448\u043b\u0430! \u041f\u043b\u044e\u0441 \u0442\u0430\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0443\u0445\u043e\u0434\u0438\u0442 \u043d\u0430 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u043c\u0443\u043b\u044c\u0442\u0438\u0433\u0440\u0430\u0444\u0430. \u0422\u0435\u0441\u0442\u044b \u0432\u0441\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0442 \u0434\u043e\u043b\u0433\u043e, \u0430 \u0438\u043d\u043e\u0433\u0434\u0430 \u043e\u0447\u0435\u043d\u044c \u0434\u043e\u043b\u0433\u043e (\u043c\u0443\u043b\u044c\u0442\u0438\u0433\u0440\u0430\u0444 \u044f \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u043b \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u043b\u044f \u0447\u0438\u0441\u0442\u043e\u0442\u044b \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u0430). \u041d\u043e \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u043c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u043f\u0435\u0440\u0435\u0434\u0438\u043b \u0432\u0441\u0435\u0445 \u0441\u0432\u043e\u0438\u0445 \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043e\u0432 (\u0435\u0441\u043b\u0438, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f\u0445 \u0438\u0445 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f, \u0431\u0440\u0430\u043b \u043a\u043e\u0434 \u0441 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0430, \u0432\u0440\u043e\u0434\u0435 \u0432\u0435\u0440\u043d\u044b\u0439)! \u0422\u0430\u043a \u0447\u0442\u043e, \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0441\u0447\u0438\u0442\u0430\u044e, \u043e\u0447\u0435\u043d\u044c \u0438 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u0435\u0439, \u043d\u0435 \u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c. \u0412\u043e\u0442 \u044d\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u0442\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \ud83d\ude09<\/p>\n
      \u0421\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435, \u043e\u043d\u0430 \u0440\u0435\u0448\u0435\u043d\u0430. \u0412\u0440\u0435\u043c\u044f \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0441\u0445\u043e\u0436\u0435 \u0434\u0430\u0436\u0435 \u0441 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u043e\u0439 \u0441 \u043a\u0443\u0447\u0435\u0439! \u0424\u043e\u0440\u0434-\u0411\u0435\u043b\u043b\u043c\u0430\u043d \u0442\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u0441\u043e \u0441\u0432\u043e\u0435\u0439 \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0435\u0439 \u0441 \u043e\u0447\u0435\u0440\u0435\u0434\u044c\u044e (SPFA) \u0441\u0438\u043b\u044c\u043d\u043e \u043e\u0442\u0441\u0442\u0430\u043b \u043e\u0442 \u043c\u043e\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438. \u042f \u0431\u044b\u043b \u043f\u0440\u0438\u044f\u0442\u043d\u043e \u0443\u0434\u0438\u0432\u043b\u0435\u043d!<\/p>\n
      \u0427\u0442\u043e \u0436, \u044f \u0440\u0435\u0448\u0438\u043b \u0435\u0449\u0435 \u043e\u0434\u043d\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u0442\u0430\u043a \u0436\u0435 3-\u043c\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438 \u043d\u0430\u00a0<\/em>\u043b\u0438\u0442\u043a\u043e\u0434\u0435<\/em><\/a>. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043d\u0438\u0436\u0435:<\/em>  <\/p>\n
        \n
      1. \n
        \u041c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/p>\n<\/li>\n<\/ol>\n
        \nHidden text<\/summary>\n
        \n
        from collections import deque   class Solution:     def networkDelayTime(self, times, n, k):          arr = [[] for _ in range(n + 1)]         graph = {}          for item in times:             arr[item[0]].append((item[1], item[2]))          queue = deque()         graph[k] = {}         for i in arr[k]:             neighbor = i[0]              graph[k][neighbor] = i[1]             queue.append(neighbor)          while queue:             current = queue.popleft()             if current not in graph:                 graph[current] = {}             for i in arr[current]:                 neighbor = i[0]                 if neighbor not in graph:                     graph[i[0]] = {}                     queue.append(neighbor)                  graph[current][neighbor] = i[1]                                               lst = deque([key for key in graph.keys()])         parents = {}         costs = {}         infinity = float('inf')                   processed = set()         while lst:             node = lst.popleft()             if node not in processed:                 for child, cost in graph[node].items():                     new_cost = cost + costs.get(node,                                                 0)                     min_cost = costs.get(child,                                          infinity)                     if new_cost < min_cost:                         costs[child] = new_cost                         parents[child] = node                         if child in processed:                             lst.appendleft(child)                             processed.remove(child)                 processed.add(node)                    max_distance = 0         for i in range(1, n + 1):             if k == i:                 continue             distance = costs.get(i, 'No')             if distance == 'No':                 return -1             if distance > max_distance:                 max_distance = distance         else:             return max_distance<\/code><\/pre>\n
        <\/figure>\n<\/p>\n<\/div>\n<\/details>\n
          \n
        1. \n
          \u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u0430:<\/p>\n<\/li>\n<\/ol>\n
          \nHidden text<\/summary>\n
          \n
          from collections import deque  class Solution:     def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:          arr = [[] for _ in range(n + 1)]         graph = {}          for item in times:             arr[item[0]].append((item[1], item[2]))           queue = deque()         graph[k] = {}         for i in arr[k]:             neighbor = i[0]             graph[k][neighbor] = i[1]             queue.append(neighbor)          while queue:             current = queue.popleft()             if current not in graph:                 graph[current] = {}             for i in arr[current]:                 neighbor = i[0]                 if neighbor not in graph:                     graph[i[0]] = {}                     queue.append(neighbor)                  graph[current][neighbor] = i[1]           infinity = float(\"inf\")         costs = {}         parents = {}         processed = set()         for v in graph[k]:             costs[v] = graph[k][v]             parents[v] = k           def find_lowest_cost_node(costs):             lowest_cost = infinity             lowest_cost_node = None             for node in costs:                 cost = costs[node]                 if cost < lowest_cost and node not in processed:                     lowest_cost = cost                     lowest_cost_node = node             return lowest_cost_node           node = find_lowest_cost_node(costs)         while node is not None:             cost = costs.get(node, infinity)             neighbors = graph[node]             for q in neighbors.keys():                 new_cost = cost + neighbors[q]                 old_cost = costs.get(q, infinity)                 if old_cost > new_cost:                     costs[q] = new_cost                     parents[q] = node             processed.add(node)             node = find_lowest_cost_node(costs)          max_val = 0         for i in range(1, n + 1):             if i == k:                 continue             value = costs.get(i, 'No')             if value == 'No':                 return -1             if value > max_val:                 max_val = value         return max_val<\/code><\/pre>\n
          <\/figure>\n<\/p>\n<\/div>\n<\/details>\n
            \n
          1. \n
            \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u0430 \u0441 \u043a\u0443\u0447\u0435\u0439:<\/p>\n<\/li>\n<\/ol>\n
            \nHidden text<\/summary>\n
            \n
            import heapq,sys from collections import defaultdict class Solution:     def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:         adj = defaultdict(list)         for t in times:             adj[t[0]].append((t[2],t[1]))         q=[]         heapq.heapify(q)         dist = [sys.maxsize]*(n)         dist[k-1]=0         heapq.heappush(q,(0,k))         while q:             d,u = heapq.heappop(q)             for weight,v in adj[u]:                 if dist[v-1]>dist[u-1]+weight:                     dist[v-1]=dist[u-1]+weight                     heapq.heappush(q,(dist[v-1],v))         for i in range(len(dist)):             if dist[i]==sys.maxsize:                 return -1         return max(dist)<\/code><\/pre>\n
            <\/figure>\n<\/p>\n<\/div>\n<\/details>\n
            \u041a\u0430\u043a \u043c\u044b \u0432\u0438\u0434\u0438\u043c, \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0435, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u0447\u0442\u043e-\u0442\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c, \u0433\u0434\u0435-\u0442\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u0442.\u0434. \u043d\u043e \u0432\u0440\u0435\u043c\u044f \u0441\u0438\u043b\u044c\u043d\u043e \u043d\u0435 \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u0441\u044f, \u0442.\u043a. \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0435 \u043d\u0430 20 \u043c\u043b\u0440\u0434 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \ud83d\ude42<\/p>\n
            \u041d\u041e! \u041c\u043e\u0439 \u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0435\u0449\u0435 \u0438 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0440\u0435\u0431\u0440\u0430\u043c\u0438 \u043c\u043e\u0436\u0435\u0442!<\/strong><\/p>\n
            \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u043d\u0435\u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0445 \u0443\u0437\u043b\u043e\u0432<\/h3>\n
            \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0443 \u043d\u0430\u0441 \u043f\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u043f\u0443\u0442\u0438 \u0441 \u0443\u0437\u043b\u0430 k \u0434\u043e \u0432\u0441\u0435\u0445 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043d\u0435 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0441\u0442\u0438\u0447\u044c \u043e\u0442 k-\u043e\u0433\u043e. \u0422\u043e\u0433\u0434\u0430 \u0432\u043d\u0435\u0441\u0435\u043c \u0432 \u043a\u043e\u0434 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u0442\u0430\u043a\u043e\u0433\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u044f. \u041a\u043e\u0434 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0432\u0441\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0442 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0434\u043e \u0432\u0441\u0435\u0445 \u0435\u043c\u0443 \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0445. \u041f\u0440\u0438 \u043f\u043e\u043f\u044b\u0442\u043a\u0435 \u0434\u043e\u0441\u0442\u0438\u0447\u044c \u043d\u0435\u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0439 \u0443\u0437\u0435\u043b, \u0432\u044b\u0432\u0435\u0434\u0435\u0442\u0441\u044f \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435.<\/p>\n
            \nHidden text<\/summary>\n
            \n
            from collections import deque  input_graph = [[1, 2, 5], [1, 3, -6],                [2, 4, 4], [2, 3, 7],                [3, 2, -2], [3, 4, 6]] n = 4 for k in range(1, 5):     print(f'\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a - \u0443\u0437\u0435\u043b {k}')     arr = [[] for _ in range(n + 1)]     graph = {}      for item in input_graph:         arr[item[0]].append((item[1], item[2]))      queue = deque()     graph[k] = {}     for i in arr[k]:         neighbor = i[0]         graph[k][neighbor] = i[1]         queue.append(neighbor)      while queue:         current = queue.popleft()         if current not in graph:             graph[current] = {}         for i in arr[current]:             neighbor = i[0]             if neighbor not in graph:                 graph[i[0]] = {}                 queue.append(neighbor)              graph[current][neighbor] = i[1]        lst = deque([key for key in graph.keys()])  # \u0424\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430     parents = {}  # {\u041d\u043e\u0434\u0430: \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c}     costs = {}  # \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 (\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0434\u043b\u0438\u043d\u044b \u043f\u0443\u0442\u0438 \u0434\u043e \u043d\u043e\u0434\u044b \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430)     infinity = float('inf')  # \u0411\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c (\u043a\u043e\u0433\u0434\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043e \u043d\u043e\u0434\u044b \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d)     processed = set()  # \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043d\u043e\u0434     cycle_count = 0     while lst:         node = lst.popleft()         if node not in processed:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0443\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0435\u0435 \u0437\u0430\u043d\u043e\u0432\u043e \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c (\u0438\u043d\u0430\u0447\u0435 \u043c.\u0431. \u0431\u0435\u0441\u043a. \u0446\u0438\u043a\u043b)             for child, cost in graph[node].items():  # \u041f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0434\u0435\u0442\u044f\u043c                 cycle_count += 1                 new_cost = cost + costs.get(node,                                             0)  # \u041f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 = \u043f\u0443\u0442\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f + \u0432\u0435\u0441 \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043d\u0435\u0442, \u0442\u043e \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u0435\u0433\u043e = 0)                 min_cost = costs.get(child,                                      infinity)  # \u0421\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0435\u0433\u043e \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0431\u044b\u043b\u043e, \u0442\u043e \u043e\u043d \u0431\u0435\u0441\u043a.)                 if new_cost < min_cost:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e \u044d\u0442\u043e\u0433\u043e,                     costs[child] = new_cost  # \u0442\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439                     parents[child] = node  # \u0422\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u0438\u043d \u043f\u0443\u0442\u044c                     if child in processed:  # UPDATE: \u0435\u0441\u043b\u0438 \u0440\u0435\u0431\u0435\u043d\u043e\u043a \u0431\u044b\u043b \u0432 \u0447\u0438\u0441\u043b\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445                         lst.appendleft(child)  # \u0412\u043d\u043e\u0432\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u0442\u0443 \u043d\u043e\u0434\u0443 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0435\u0433\u043e \u0437\u0430\u043d\u043e\u0432\u043e                         processed.remove(child)  # \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0438\u0437 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445             processed.add(node)  # \u041a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u0434\u0435\u0442\u0438 (\u0440\u0435\u0431\u0440\u0430 \u0433\u0440\u0430\u0444\u0430) \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b, \u0432\u043d\u043e\u0441\u0438\u043c \u043d\u043e\u0434\u0443 \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445      print(f'\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: {cycle_count}')      print(f'\u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u043d\u043e\u0434\u044b: {costs}')     print(f'\u0420\u043e\u0434\u0438\u0442\u0435\u043b\u0438 \u043d\u043e\u0434, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b: {parents}')      def get_shortest_path(start, end):         '''         \u041f\u0440\u043e\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f\u043c, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438,         \u0442.\u0435. \u0438\u0449\u0435\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438, \u043f\u043e\u0442\u043e\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0438 \u0442.\u0434. \u043f\u043e\u043a\u0430 \u043d\u0435 \u0434\u043e\u0439\u0434\u0435\u0442 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0443\u0442\u0438.         \u0422\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u0443\u044e \u0446\u0435\u043f\u043e\u0447\u043a\u0443 \u043d\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u044b \u0438\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432 \u043a\u043e\u043d\u0446\u0435, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c         \u0438\u0441\u0442\u0438\u043d\u043d\u044b\u0439 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c         '''         parent = parents.get(end, 'No')  # \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u0430 \u043b\u0438 \u043d\u043e\u0434\u0430         if parent == 'No':             return f'\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 {start} \u0434\u043e {end}: \u0443\u0437\u0435\u043b \u043d\u0435\u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c. \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e'         result = [end]         while parent != start:             result.append(parent)             parent = parents[parent]         result.append(start)         result.reverse()         result = map(str, result)  # \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0435\u0441\u043b\u0438 \u0438\u043c\u0435\u043d\u0430 \u043d\u043e\u0434 \u0431\u0443\u0434\u0443\u0442 \u0447\u0438\u0441\u043b\u0430\u043c\u0438, \u0430 \u043d\u0435 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 (\u0434\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e join)         shortest_distance = costs[end]         print('-->'.join(result))          return f'\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 {start} \u0434\u043e {end}:  {shortest_distance}'        for i in range(1, n+1):         if i == k:             continue         print(get_shortest_path(start=k, end=i)) <\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n
            \u0412\u044b\u0432\u043e\u0434\u044b<\/h2>\n
            \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442!<\/em><\/strong> \u041f\u0440\u0438\u0447\u0435\u043c \u0441 \u043d\u0435\u043f\u043b\u043e\u0445\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c\u044e. \u0415\u0441\u043b\u0438 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0442\u043e, \u0447\u0442\u043e \u0435\u0449\u0435 \u0438 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0432\u0435\u0441\u0430\u043c\u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 — \u0442\u043e \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0442\u043b\u0438\u0447\u043d\u043e! \u041d\u043e \u0435\u0441\u043b\u0438 \u0432 \u0437\u0430\u0434\u0430\u0447\u0435 \u0443\u043a\u0430\u0437\u0430\u043d\u043e, \u0447\u0442\u043e \u043d\u0435\u0442 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0440\u0435\u0431\u0435\u0440, \u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435-\u0442\u0430\u043a\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u043e\u0439 \u0441 \u043a\u0443\u0447\u0435\u0439. \u0415\u0441\u043b\u0438 \u043c\u0430\u043b\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u0430\u043c\u0430 \u043d\u0435 \u0437\u043d\u0430\u0435\u0442, \u0435\u0441\u0442\u044c \u043b\u0438 \u0442\u0430\u043c \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043c\u0435\u043b\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043c\u043e\u0438\u043c (\u043d\u0430\u0432\u0435\u0440\u043d\u043e\u0435, \u0442\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0443\u0436\u0435 \u0441\u043a\u0430\u0437\u0430\u0442\u044c) \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c. <\/p>\n
            (UPD) \u041c\u0435\u043d\u044f \u043e\u043f\u0435\u0440\u0435\u0434\u0438\u043b\u0438…<\/h2>\n
            \u0421\u043f\u0443\u0441\u0442\u044f \u043f\u043e\u0447\u0442\u0438 30\u043a \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u043e\u0432 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430 \u043e\u0434\u0438\u043d \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u0430\u043b \u043c\u043d\u0435, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043b, \u043d\u043e \u0438\u043c \u043e\u0447\u0435\u043d\u044c \u0440\u0435\u0434\u043a\u043e \u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f, \u043c\u0430\u043b\u043e \u043a\u0442\u043e \u043e \u043d\u0435\u043c \u0432\u043e\u043e\u0431\u0449\u0435 \u0437\u043d\u0430\u0435\u0442 \u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u043d\u0435\u043c \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u043c\u0435\u043d\u044c\u0448\u0435, \u0445\u043e\u0442\u044f \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430\u0438\u0431\u044b\u0441\u0442\u0440\u0435\u0439\u0448\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u043d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0438\u0439 \u0434\u0435\u043d\u044c. \u041d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041b\u0435\u0432\u0438\u0442\u0430. <\/em><\/strong>\u0415\u0433\u043e \u0438\u0434\u0435\u044f \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043c\u043e\u0435\u0439 (\u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u0433\u0440\u0430\u0444 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u0438). \u0415\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u044d\u0442\u043e\u0439 \u0438\u0434\u0435\u0438 \u043b\u0435\u0436\u0438\u0442 \u0432 \u0441\u0430\u043c\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u0430 \u043d\u0435 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435. \u0414\u0430 \u0438 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u043e\u0436\u0435 \u0432 \u0441\u0430\u043c\u043e\u043c \u0442\u0435\u043b\u0435 \u0446\u0438\u043a\u043b\u0430 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e \u043e\u0431\u0445\u043e\u0434\u0438\u043b \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0433\u0440\u0430\u0444 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u0438, \u0442.\u0435. \u043f\u0440\u0435\u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0438\u043d\u0433 \u043c\u043e\u0439 \u0431\u044b\u043b \u043f\u043e \u0441\u0443\u0442\u0438 \u043d\u0435 \u043d\u0443\u0436\u0435\u043d. \u041c\u043d\u0435 \u0432 \u0433\u043e\u043b\u043e\u0432\u0443 \u044d\u0442\u043e \u043d\u0435 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043b\u043e, \u043d\u043e \u044f \u043f\u043e \u0441\u0443\u0442\u0438 \u0434\u0435\u043b\u0430\u043b \u043b\u0438\u0448\u043d\u044e\u044e \u0440\u0430\u0431\u043e\u0442\u0443. \u041d\u043e \u0441\u0430\u043c\u0430 \u0438\u0434\u0435\u044f \u043c\u043d\u0435 \u043f\u0440\u0438\u0448\u043b\u0430 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0435 \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u043f\u043e\u0434\u0432\u0435\u043b\u0430, \u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043b\u0443\u0447\u0448\u0435. \u0410 \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043b\u0438\u0448\u044c \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0433\u0440\u0430\u0444\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0441 \u043d\u0438\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c. \u041f\u043e \u0441\u0443\u0442\u0438, \u0443 \u043c\u0435\u043d\u044f \u0432\u044b\u0448\u043b\u0430 \u0442\u043e\u0447\u043d\u0430\u044f \u0435\u0433\u043e \u043a\u043e\u043f\u0438\u044f, \u043d\u043e \u0441 «\u043b\u0438\u0448\u043d\u0438\u043c» \u043f\u0440\u0435\u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0438\u043d\u0433\u043e\u043c.<\/p>\n
            \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 2 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u041b\u0435\u0432\u0438\u0442\u0430. \u0421 \u043e\u0434\u043d\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u044c\u044e \u0438 2-\u043c\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044f\u043c\u0438. \u041a\u043e\u043c\u0443 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u043c\u043e\u0436\u0435\u0442\u0435 \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f (\u043f\u0440\u0430\u0432\u0434\u0430 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u043d\u0435\u043c \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u043c\u043d\u043e\u0433\u043e, \u043d\u043e \u0432\u0441\u0435 \u0436\u0435 \u0435\u0441\u0442\u044c). \u0422\u0430\u043a \u0432\u043e\u0442, \u043c\u043e\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0431\u044b\u043b\u0430 \u0441 \u043e\u0434\u043d\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u044c\u044e. \u041e\u043d\u0430 \u0432 \u043e\u0447\u0435\u043d\u044c \u0440\u0435\u0434\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u0441 2-\u043c\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044f\u043c\u0438. \u041d\u043e «\u043c\u043e\u0439» \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u043b\u0435\u0433\u043a\u043e \u043f\u0435\u0440\u0435\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u043e\u0434 2 \u043e\u0447\u0435\u0440\u0435\u0434\u0438, \u0438 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432\u0440\u0435\u043c\u044f, \u043d\u0435 \u0441\u0447\u0438\u0442\u0430\u044f \u043f\u0440\u0435\u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0438\u043d\u0433\u0430, \u0431\u0443\u0434\u0435\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c. \u0414\u0430 \u043f\u043e \u0441\u0443\u0442\u0438 \u044d\u0442\u043e \u0438 \u0431\u0443\u0434\u0435\u0442 \u0441\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041b\u0435\u0432\u0438\u0442\u0430 \u0441 2-\u043c\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044f\u043c\u0438, \u043f\u0440\u043e\u0441\u0442\u043e \u0441 \u043b\u0438\u0448\u043d\u0438\u043c\u0438 \u0442\u0435\u043b\u043e\u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f\u043c\u0438 \u0438 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0433\u0440\u0430\u0444\u0430, \u0432 \u043e\u0431\u0449\u0435\u043c, \u0441\u043b\u0435\u0433\u043a\u0430 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u043d\u044b\u0439, \u043d\u043e \u0441\u0443\u0442\u044c \u0442\u0430 \u0436\u0435. \u041a\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/p>\n
            def levit(graph: List[List[int]], n: int, k: int):     graph = [[] for _ in range(n + 1)]     for [node1, node2, w] in input_graph:         graph[node1].append((node2, w))      infinity = float('inf')     costs = [infinity] * (n + 1)     costs[k] = 0      processed = [False] * (n + 1)     unprocessed = [True] * (n + 1)     unprocessed[k] = False      nq = deque([k])     uq = deque()     cycle_count = 0     while nq or uq:         i = uq.popleft() if uq else nq.popleft()         parent_cost = costs[i]         edges = graph[i]         for (j, w) in edges:             cycle_count += 1             new_cost = parent_cost + w             if unprocessed[j]:                 costs[j] = new_cost                 nq.append(j)                 unprocessed[j] = False                 continue              if costs[j] > new_cost:                 costs[j] = new_cost                 if processed[j]:                     uq.append(j)                     processed[j] = False          processed[i] = True      return costs[1:], cycle_count<\/code><\/pre>\n
            \"\u0421\u0440\u0435\u0434\u043d\u0435\u0435<\/p>\n
            \u0421\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043f\u043e 16 \u0441\u0442\u0440\u0435\u0441\u0441 \u0442\u0435\u0441\u0442\u0430\u043c<\/figcaption><\/div>\n<\/figure>\n
            \u041a\u0430\u043a \u0432\u0438\u0434\u0438\u043c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041b\u0435\u0432\u0438\u0442\u0430 \u043f\u043e\u043a\u0430\u0437\u0430\u043b \u0441\u0435\u0431\u044f \u0441\u0430\u043c\u044b\u043c \u0431\u044b\u0441\u0442\u0440\u044b\u043c \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445. «\u041c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c» (\u041b\u0435\u0432\u0438\u0442 \u0441 \u043e\u0434\u043d\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u044c\u044e) \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u043c\u0435\u0441\u0442\u0435, \u0431\u0435\u0437 \u043f\u0440\u0435\u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0438\u043d\u0433\u0430 \u0431\u044b\u043b \u0431\u044b \u0435\u0449\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u041d\u043e \u0443 \u044d\u0442\u043e\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u0435\u0441\u0442\u044c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438 \u043e\u0447\u0435\u043d\u044c «\u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c» \u0433\u0440\u0430\u0444\u0435 \u0432\u0437\u043b\u0435\u0442\u0438\u0442 \u0434\u043e \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439. \u041f\u043e\u044d\u0442\u043e\u043c\u0443, \u043b\u0443\u0447\u0448\u0435 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0441 2-\u043c\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044f\u043c\u0438, \u0442\u0430\u043c \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043d\u0435\u0442.<\/p>\n
            \u0418\u0442\u043e\u0433\u0438<\/h2>\n
            \u0427\u0442\u043e \u0436, \u0447\u0435\u0441\u0442\u043d\u043e \u043f\u0440\u0438\u0437\u043d\u0430\u044e\u0441\u044c, \u044f \u0441\u0438\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u0442\u0440\u043e\u0438\u043b\u0441\u044f, \u043a\u043e\u0433\u0434\u0430 \u0443\u0437\u043d\u0430\u043b, \u0447\u0442\u043e \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \ud83d\ude41 \u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043d \u043e\u0447\u0435\u043d\u044c «\u043d\u0435 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0439». \u0412 \u0443\u0447\u0435\u0431\u043d\u044b\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430\u0445 \u043d\u0438 \u0440\u0430\u0437\u0443 \u043d\u0435 \u0441\u043b\u044b\u0448\u0430\u043b \u043e\u0431 \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u043d\u0438\u0438 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0414\u0430 \u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u0440\u0443\u0441\u0441\u043a\u043e\u044f\u0437\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043e\u0447\u0435\u043d\u044c \u0441\u043a\u0443\u0434\u0435\u043d. \u0412 \u0430\u043d\u0433\u043b\u043e\u044f\u0437\u044b\u0447\u043d\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043f\u043e-\u0434\u0440\u0443\u0433\u043e\u043c\u0443. \u0414\u0430\u0436\u0435 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u044d\u0442\u043e\u0439 \u043f\u043b\u043e\u0449\u0430\u0434\u043a\u0435, \u0441\u0443\u0434\u044f \u043f\u043e \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043d\u0438\u043a\u0442\u043e \u0434\u043e\u043b\u0433\u043e \u043c\u043d\u0435 \u043d\u0435 \u0433\u043e\u0432\u043e\u0440\u0438\u043b \u043e \u043d\u0435\u043c, \u043d\u0435 \u0437\u043d\u0430\u043b\u0438 \u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0438 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430…<\/p>\n
            \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u044f \u043f\u044b\u0442\u0430\u043b\u0441\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438. 
            \u041f\u0435\u0440\u0432\u043e\u0435 \u0447\u0443\u0432\u0441\u0442\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u043d\u044f \u043f\u043e\u0441\u0435\u0442\u0438\u043b\u043e \u0432 \u043c\u043e\u043c\u0435\u043d\u0442 \u0437\u043d\u0430\u043a\u043e\u043c\u0441\u0442\u0432\u0430 \u0441 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0431\u044b\u043b\u043e \u043e\u0442\u0447\u0430\u044f\u043d\u0438\u0435… \u0414\u0443\u043c\u0430\u043b, \u0447\u0442\u043e \u0437\u0440\u044f \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u043b \u0440\u0430\u0431\u043e\u0442\u0443, \u0434\u0443\u043c\u0430\u043b, \u0441\u043c\u043e\u0433\u0443 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043c\u0438\u0440 \u0447\u0443\u0442\u043e\u0447\u043a\u0443 \u043b\u0443\u0447\u0448\u0435, \u043d\u043e \u0432\u0441\u0435 \u0431\u044b\u043b\u043e \u0437\u0440\u044f. \u041e\u0434\u043d\u0430\u043a\u043e, \u044f \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b \u043d\u0430 \u044d\u0442\u043e \u0442\u0440\u0435\u0437\u0432\u043e \u0438 \u043c\u0435\u043d\u044f \u043f\u043e\u0441\u0435\u0442\u0438\u043b\u0430 \u043c\u044b\u0441\u043b\u044c: «\u0422\u044b \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u0448\u0435\u043b \u043a \u0441\u0430\u043c\u043e\u043c\u0443 \u0431\u044b\u0441\u0442\u0440\u043e\u043c\u0443 \u043d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0438\u0439 \u0434\u0435\u043d\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443, \u0434\u0430 \u0442\u044b \u043e\u0433\u043e\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e!».  \u041f\u043b\u044e\u0441 \u044f \u043f\u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u043b \u0412\u0430\u0441, \u0434\u043e\u0440\u043e\u0433\u0438\u0435 \u0434\u0440\u0443\u0437\u044c\u044f, \u0441 \u044d\u0442\u0438\u043c \u0440\u0435\u0434\u043a\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c, \u043f\u043e\u043b\u044c\u0437\u0443\u0439\u0442\u0435\u0441\u044c \u043d\u0430 \u0437\u0434\u043e\u0440\u043e\u0432\u044c\u0435!<\/p>\n
            \u0412\u0441\u0435\u043c \u0441\u043f\u0430\u0441\u0438\u0431\u043e, \u0440\u0430\u0434 \u0431\u044b\u043b \u043f\u043e\u043e\u0431\u0449\u0430\u0442\u044c\u0441\u044f, \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043a\u0438 \u0438 \u043f\u043e\u043f\u044b\u0442\u043a\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c «\u043c\u043e\u0439» \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u041f\u043e\u043b\u0443\u0447\u0438\u043b \u043e\u043f\u044b\u0442, \u0443\u0434\u043e\u0432\u043e\u043b\u044c\u0441\u0442\u0432\u0438\u0435, \u0438, \u043d\u0430\u0434\u0435\u044e\u0441\u044c, \u0432\u044b \u0442\u043e\u0436\u0435. \u0412\u0441\u0435\u043c \u0434\u043e\u0431\u0440\u0430!<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n
            <\/div>\n

             \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habr.com\/ru\/articles\/811051\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
            <\/div>\n
            \n
            \n
            \n
            \n
            \u0412\u0441\u0435\u043c \u043f\u0440\u0438\u0432\u0435\u0442! \u042f \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043b, \u043f\u043e\u0445\u043e\u0436\u0435, \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0440\u0435\u0431\u0440\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430.<\/p>\n
            \u041f\u043e\u0447\u0435\u043c\u0443 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439? \u042f \u0438\u0441\u043a\u0430\u043b \u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u043d\u0435 \u043d\u0430\u0448\u0435\u043b, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043e\u043d\u043e \u0443\u0436\u0435 \u0431\u044b\u043b\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e, \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043b\u043e\u0445\u043e \u043f\u043e\u0438\u0441\u043a\u0430\u043b. \u0416\u0434\u0443 \u041d\u043e\u0431\u0435\u043b\u0435\u0432\u0441\u043a\u0443\u044e \u043f\u0440\u0435\u043c\u0438\u044e =)<\/p>\n
            \u0414\u043e\u0434\u0443\u043c\u0430\u043b\u0441\u044f \u044f \u0434\u043e \u043d\u0435\u0433\u043e \u043f\u0443\u0442\u0435\u043c \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. \u041f\u0440\u043e\u0448\u0443 \u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u043e \u043e\u0442\u043d\u0435\u0441\u0442\u0438\u0441\u044c \u043a \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u043c\u0443, \u0438\u0431\u043e \u044d\u0442\u043e \u043c\u043e\u044f \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f, \u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044f \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u044b\u0432\u0430\u043b  \u0438, \u0432\u043e\u043e\u0431\u0449\u0435, \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432\u043e\u0432\u0441\u0435 (\u043d\u043e \u043f\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c \u0442\u0435\u0441\u0442\u0430\u043c \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e).<\/p>\n
            \u041f\u043e\u0432\u0442\u043e\u0440\u044e\u0441\u044c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0440\u0435\u0431\u0440\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430<\/strong> (\u043d\u043e \u043d\u0435 \u0441 \u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438). \u0427\u0435\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430?<\/p>\n
            \u042d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e! \u0423 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 O(En), \u0433\u0434\u0435 n — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432, \u0415 — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0431\u0435\u0440. \u0423 «\u043c\u043e\u0435\u0433\u043e» \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0442\u0430\u043a\u0430\u044f \u0436\u0435 \u0430\u0441\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c. \u041d\u043e \u043f\u043e \u043c\u043e\u0438\u043c \u0440\u0430\u0441\u0447\u0435\u0442\u0430\u043c \u0445\u0443\u0434\u0448\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f. \u0410 \u0443 \u0411\u0435\u043b\u043b\u043c\u0430\u043d\u0430-\u0424\u043e\u0440\u0434\u0430 \u0445\u0443\u0434\u0448\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435 (\u043e\u0431 \u044d\u0442\u043e\u043c \u0434\u0430\u043b\u0435\u0435). \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e O(n2<\/sup>+E). \u041e\u0431 \u044d\u0442\u043e\u043c \u0442\u043e\u0436\u0435 \u043d\u0430\u043f\u0438\u0448\u0443 \u0434\u0430\u043b\u0435\u0435. \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Python:<\/em><\/strong><\/p>\n
            P.S.<\/h4>\n
            \u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u044b \u043c\u043d\u043e\u0433\u0438\u0435 \u043c\u043e\u043c\u0435\u043d\u0442\u044b, \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0443 \u0437\u0430 \u0442\u0435\u0441\u0442-\u043a\u0435\u0439\u0441\u044b \u0438 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043a\u0438. \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438 \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u044b\u043c\u0438 (\u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0441\u0430\u0440\u043a\u0430\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438-\u043e\u0441\u043a\u043e\u0440\u0431\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435), \u0442.\u043a. \u044f \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u043b \u0440\u0430\u0431\u043e\u0442\u043e\u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n
            \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n
            \n
            \u041f\u0440\u0438\u043c\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c<\/figcaption><\/div>\n<\/figure>\n
            \u0418\u0442\u0430\u043a, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0433\u0440\u0430\u0444 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c \u043c\u0435\u0436\u0434\u0443 2-\u043c \u0438 5-\u043c \u0443\u0437\u043b\u043e\u043c. \u041d\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 — \u043d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 (1-\u0433\u043e \u0443\u0437\u043b\u0430) \u0434\u043e 9-\u0433\u043e \u0443\u0437\u043b\u0430 (\u043b\u0438\u0431\u043e \u0434\u043e \u043b\u044e\u0431\u043e\u0433\u043e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u043e\u0433\u043e).<\/p>\n
            \u0413\u0440\u0430\u0444 \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0432 \u0432\u0438\u0434\u0435 \u0445\u044d\u0448 \u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u0433\u0434\u0435:<\/p>\n
            graph = {
             \u043d\u043e\u0434\u0430_1_(\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a): {\u0441\u043e\u0441\u0435\u0434_1: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, \u0441\u043e\u0441\u0435\u0434_2: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, …},
             \u043d\u043e\u0434\u0430_2: {\u0441\u043e\u0441\u0435\u0434_1: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, \u0441\u043e\u0441\u0435\u0434_2: \u0432\u0435\u0441 \u0434\u043e \u043d\u0435\u0433\u043e, …},
             …
             }<\/em><\/p>\n
            graph = {     1: {2: 10, 3: 6, 4: 8},     2: {7: 11, 4: 5, 5: -4},     3: {5: 3},     4: {7: 12, 3: 2, 5: 5, 6: 7},     5: {6: 9, 9: 12},     6: {8: 8, 9: 10},     7: {6: 4, 8: 6, 9: 16},     8: {9: 15},     9: {} }<\/code><\/pre>\n
            \u0412\u0430\u0436\u043d\u043e! <\/strong>\u041d\u0443\u0436\u043d\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u0433\u0440\u0430\u0444\u0430 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0438\u0445 \u043e\u0442\u0434\u0430\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u0422.\u0435. \u0441\u043f\u0435\u0440\u0432\u0430 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043e\u043f\u0438\u0441\u0430\u043b\u0438 \u0438\u0445, \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0430\u0435\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0441\u043e\u0441\u0435\u0434\u044f\u043c \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u0422.\u0435. \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043f\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e, \u0431\u0443\u0434\u0442\u043e \u044d\u0442\u043e \u043d\u0435 \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u0430 \u043e\u0431\u044b\u043a\u043d\u043e\u0432\u0435\u043d\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0433\u0434\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0435\u043c \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. \u0412 Python \u0441\u043b\u043e\u0432\u0430\u0440\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u043c\u0438 (\u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0432\u0435\u0440\u0441\u0438\u0438 3.6), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u043c \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u0438\u0431\u0435\u0433\u0430\u0442\u044c \u043a \u0434\u0440\u0443\u0433\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430\u043c \u0434\u0430\u043d\u043d\u044b\u0445, \u0442\u0438\u043f\u0430 Ordered dict<\/em> \u0438\u0437 \u043c\u043e\u0434\u0443\u043b\u044f collections<\/em>.
            \u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u0433\u0440\u0430\u0444 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0435\u0439, \u043d\u043e \u043c\u043d\u0435 \u0442\u0430\u043a \u043f\u0440\u043e\u0449\u0435.<\/p>\n\n
            P.S. \u0422\u043e\u0442, \u043a\u0442\u043e \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c:<\/strong><\/p>\n
            \n
            \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u0437\u043d\u0430\u0435\u0442\u0435? \u041d\u0430\u0431\u043e\u0440 \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0434\u0443\u0433, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u0443\u0433\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0430\u0440\u0430\u043c\u0438 \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u043f\u043b\u044e\u0441\u043e\u043c \u0432\u0435\u0441\u0430 \u0434\u043b\u044f \u0434\u0443\u0433 \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0438. \u041d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0442\u0430\u043c \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u043d\u0435 \u043f\u0440\u0435\u0434\u0443\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043e.<\/p>\n<\/blockquote>\n
            \u0417\u0430\u0440\u0430\u043d\u0435\u0435 \u043e\u0442\u0432\u0435\u0447\u0430\u044e.<\/p>\n
            \u0425\u043e\u0440\u043e\u0448\u043e, \u0431\u0443\u0434\u0443 \u043e\u0442 \u0432\u0430\u0448\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043e\u0442\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u0442\u044c\u0441\u044f. \u0423 \u043d\u0430\u0441 \u043a\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430? \u041d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 \u0410 \u0432 \u0442\u043e\u0447\u043a\u0443 \u0412. \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0432 \u0432\u0430\u0448\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0433\u0440\u0430\u0444\u0430 \u0442\u043e\u0447\u043a\u0443 \u0410 \u0438 \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439. \u041f\u043e\u0442\u043e\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u044d\u0442\u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u0442.\u0434. \u0412\u043e\u0442 \u044d\u0442\u043e «\u043d\u0430\u0445\u043e\u0434\u0438\u043c» \u0432 \u0432\u0430\u0448\u0435\u0439 \u0431\u0435\u0441\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430 N \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f N \u0440\u0430\u0437. \u042d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043d\u043e\u0434\u044b \u0443 \u0432\u0430\u0441 \u043f\u0440\u043e\u0441\u0442\u043e \u0431\u0435\u0441\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u043d\u043e \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u044b \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 (\u0435\u0441\u043b\u0438 \u0432\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0435 \u044d\u0442\u0443 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f). \u041e\u0431\u044b\u0447\u043d\u043e \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0434\u044b \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c \u044f\u0447\u0435\u0439\u043a\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 \u0434\u043e\u0441\u0442\u0443\u043f \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443. \u0412 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b (\u043d\u0435 \u044f \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b \u0435\u0433\u043e) \u043a\u0430\u043a \u0440\u0430\u0437 \u0442\u0430\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u0438\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0433\u0440\u0430\u0444\u0430, \u0433\u0434\u0435 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0434\u044b (\u0438\u043b\u0438 \u0431\u0443\u043a\u0432\u0430 \u0432 \u043b\u0435\u043a\u0441\u0438\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435) \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c \u044f\u0447\u0435\u0439\u043a\u0438 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435. \u0422\u043e, \u043a\u0430\u043a \u0432\u044b \u043f\u044b\u0442\u0430\u0435\u0442\u0435\u0441\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0433\u0440\u0430\u0444 — \u044d\u0442\u043e \u043f\u043e \u0441\u0443\u0442\u0438 \u0432\u044b\u0441\u0442\u0440\u0435\u043b \u0441\u0435\u0431\u0435 \u0432 \u043d\u043e\u0433\u0443. \u0415\u0441\u043b\u0438 \u043e\u0442\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0439 \u0436\u0438\u0437\u043d\u0438, \u043d\u0443\u0436\u043d\u043e \u0435\u0449\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0433\u0440\u0430\u0444\u0430. \u0423\u0441\u043b\u043e\u0432\u043d\u043e \u0442\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u0448\u044c\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043a\u0435 1, \u043c\u043d\u0435 \u043d\u0430\u0434\u043e \u0432 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043e\u043a 10. \u0410 \u0434\u0430\u0439 \u043a\u0430 \u0433\u043b\u044f\u043d\u0443, \u043a\u0430\u043a\u0438\u0435 \u0442\u0430\u043c \u0434\u043e\u0440\u043e\u0433\u0438 \u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0438\u0437 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043a\u0430 7 \u0438 \u0437\u0430\u043f\u0438\u0448\u0443. \u0425\u043e\u0442\u044f \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0434\u043e\u0440\u043e\u0433\u0438 \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043a\u0430 2. \u0412 \u043e\u0431\u0449\u0435\u043c, \u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u0435 \u0432\u0430\u0448\u0435 \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043d\u043e \u044d\u0442\u043e \u0432\u0441\u0451 \u043e\u0431\u0449\u0435\u043f\u0440\u0438\u043d\u044f\u0442\u0430\u044f \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u0430, \u044f \u044d\u0442\u043e \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u044b\u0432\u0430\u043b.<\/em> 
            \u041f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0436\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u0441\u044f \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u043d\u0438\u043a\u0430\u043a \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/strong><\/p>\n
            \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0435\u0441\u043b\u0438 \u0434\u0430\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0430, \u0433\u0434\u0435 \u043d\u0430 \u0432\u0445\u043e\u0434 \u043f\u043e\u0434\u0430\u0435\u0442\u0441\u044f \u0433\u0440\u0430\u0444 \u0432\u0438\u0434\u0430: input_graph = [[\u0443\u0437\u0435\u043b_2, \u0443\u0437\u0435\u043b_5, \u0432\u0435\u0441 \u0434\u043e \u0443\u0437\u043b\u0430_5], [\u0443\u0437\u0435\u043b_7, \u0443\u0437\u0435\u043b_1, \u0432\u0435\u0441 \u0434\u043e \u0443\u0437\u043b\u0430_1] …], \u0447\u0438\u0441\u043b\u043e n — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432, k — \u0443\u0437\u0435\u043b-\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0432\u0441\u0435\u0445 \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0445<\/em> \u0432\u0435\u0440\u0448\u0438\u043d (\u043e\u0431\u044b\u0447\u043d\u043e \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b, \u043d\u043e \u0435\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u044d\u0442\u043e\u0439 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0438 \u043d\u0435\u0442, \u0442\u043e \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442, \u044d\u0442\u0443 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u044f \u0442\u0430\u043a \u0436\u0435 \u043f\u043e\u043a\u0430\u0436\u0443). \u041a\u043e\u0434 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043c\u043e\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0431\u0443\u0434\u0435\u0442 \u0442\u0430\u043a\u043e\u0439:<\/p>\n
            from collections import deque  input_graph = [[1, 2, 10], [2, 1, 10], [3, 2, 1]]  n = int(input())  # 3 k = int(input())  # 1  arr = [[] for _ in range(n + 1)] graph = {}  for item in input_graph:     arr[item[0]].append((item[1], item[2]))  queue = deque() graph[k] = {} for i in arr[k]:     neighbor = i[0]     graph[k][neighbor] = i[1]     queue.append(neighbor)  while queue:     current = queue.popleft()     if current not in graph:         graph[current] = {}     for i in arr[current]:         neighbor = i[0]         if neighbor not in graph:             graph[i[0]] = {}             queue.append(neighbor)          graph[current][neighbor] = i[1]  # -> graph = {1: {2: 10}, 2: {1: 10}} # 3-\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u0442.\u043a. \u043e\u043d\u0430 \u043d\u0435\u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u0430 \u0441 1-\u043e\u0439 \u043d\u043e\u0434\u044b! # \u0415\u0441\u043b\u0438 \u0431\u044b k=3, \u0442\u043e\u0433\u0434\u0430: # graph = {3: {2: 1}, 2: {1: 10}, 1: {2: 10}}}<\/code><\/pre>\n
            \u0421 \u044d\u0442\u0438\u043c \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u0438\u0434\u0435\u043c \u0434\u0430\u043b\u044c\u0448\u0435.<\/p>\n\n
            \u0422\u0430\u043a \u0436\u0435 \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0435\u0449\u0435 2 \u0445\u044d\u0448 \u0442\u0430\u0431\u043b\u0438\u0446\u044b.
             \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b \u0432 \u0432\u0438\u0434\u0435:
             costs = {
             \u043d\u043e\u0434\u0430_1_(\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a): 0,
             \u043d\u043e\u0434\u0430_2: infinity,
             \u043d\u043e\u0434\u0430_3: infinity,
             …
             }
            \u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043c\u044b \u0435\u0435 \u0431\u0443\u0434\u0435\u043c \u043f\u043e \u043c\u0435\u0440\u0435 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u043e «\u0434\u0435\u0442\u044f\u043c» \u0443\u0437\u043b\u043e\u0432.<\/p>\n
            costs = {}  # \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 (\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0434\u043b\u0438\u043d\u044b \u043f\u0443\u0442\u0438 \u0434\u043e \u043d\u043e\u0434\u044b \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430)<\/code><\/pre>\n
            \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u043d\u043e\u0434, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u044b:<\/p>\n
            parents = {}  # {\u041d\u043e\u0434\u0430: \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c}<\/code><\/pre>\n
            \u0415\u0435 \u0442\u0430\u043a \u0436\u0435 \u0431\u0443\u0434\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043f\u043e \u043c\u0435\u0440\u0435 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u043e \u0434\u0435\u0442\u044f\u043c \u0443\u0437\u043b\u043e\u0432.<\/p>\n
            \u041a\u0430\u043a \u0438 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0431\u0443\u0434\u0435\u043c \u043e\u0442\u043c\u0435\u0447\u0430\u0442\u044c \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0434\u043e \u0443\u0437\u043b\u043e\u0432 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c\u044e. \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u044d\u0442\u0443 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e:<\/p>\n
            infinity = float('inf')  # \u0411\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c (\u043a\u043e\u0433\u0434\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043e \u043d\u043e\u0434\u044b \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d)<\/code><\/pre>\n
            \u0414\u0430\u043b\u0435\u0435 \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043f\u0443\u0441\u0442\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e. \u0422\u0430\u043c \u0431\u0443\u0434\u0443\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b (\u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442 «\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435», \u043f\u043e\u044f\u0441\u043d\u044e \u0434\u0430\u043b\u0435\u0435, \u0430 \u043f\u043e\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e)<\/p>\n
            processed = set()  # \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043d\u043e\u0434<\/code><\/pre>\n
            \u0412\u0432\u0435\u0434\u0435\u043c \u043d\u043e\u0432\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 — \u0441\u043f\u0438\u0441\u043e\u043a \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430.<\/p>\n
            lst = deque([key for key in graph.keys()])  # \u0424\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430<\/code><\/pre>\n
            \u041f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c \u043a \u0441\u0430\u043c\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443!<\/strong><\/p>\n
              \n
            1. \n
              \u041d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 (\u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430). \u0421\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0432\u0435\u0441\u0430 \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 costs<\/em>. \u041f\u0443\u0442\u044c \u0434\u043e \u043d\u0438\u0445 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439, \u0430 \u043b\u044e\u0431\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0443\u0436\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c \u0432\u0435\u0441\u0430. \u0422\u0430\u043a \u0436\u0435 \u0432\u043d\u043e\u0441\u0438\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u0432\u0441\u0435\u0445 \u0443\u0437\u043b\u043e\u0432, \u0442.\u043a. \u043c\u044b \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b\u0438 \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u043e\u0434\u044b  \u043a\u043e\u0440\u043e\u0447\u0435. \u041a\u043e\u0433\u0434\u0430 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0432\u043d\u043e\u0441\u0438\u043c \u043d\u0430\u0448 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 processed<\/em> (\u044d\u0442\u043e\u0442 \u0443\u0437\u0435\u043b \u043c\u044b \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c).<\/p>\n<\/li>\n
            2. \n
              \u0417\u0434\u0435\u0441\u044c \u0432\u0430\u0436\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0438 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. \u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e \u0432\u0435\u0441\u0443<\/em> \u043d\u0435\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b, \u0430 \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u043e\u0431\u0449\u0435 \u0412\u0421\u0415\u0425<\/strong> \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043f\u043e\u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e. \u0422.\u0435. \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0441\u043e\u0441\u0435\u0434\u0438 \u043f\u043e\u0441\u043b\u0435 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u044d\u0442\u0430\u043f\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.
               \u041c\u044b \u043f\u043e\u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e \u0442\u0430\u043a \u0436\u0435 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u0443\u0436\u0435 \u0438\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u0441\u0430. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0432\u043d\u0435\u0441\u0435\u043d\u043d\u044b\u0439 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443, \u0442\u043e \u043c\u044b \u0435\u0433\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c. \u0422\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 parents<\/em>.
              \u041a\u043e\u0433\u0434\u0430 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u0432\u043d\u043e\u0441\u0438\u043c \u0443\u0437\u0435\u043b \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445. \u0422.\u0435. \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445<\/strong> — \u044d\u0442\u043e \u0442\u0435 \u0443\u0437\u043b\u044b, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439!<\/p>\n<\/li>\n
            3. \n
              \u0418 \u0442\u0430\u043a \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u043f\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e (\u043d\u0435 \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0430\u0435\u043c \u043a \u0441\u043e\u0441\u0435\u0434\u044f\u043c \u0441\u043e\u0441\u0435\u0434\u0435\u0439, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439), \u043f\u043e\u043a\u0430 \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b \u0432\u0441\u0435 \u0443\u0437\u043b\u044b.<\/p>\n<\/li>\n
            4. \n
              \u0421\u043f\u0438\u0441\u043e\u043a \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u0438 \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0443\u0436\u0438\u0442\u044c \u043d\u0430\u0448\u0435\u0439 \u0438\u0442\u0435\u0440\u0430\u0431\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430. \u0417\u0430\u0447\u0435\u043c? \u0415\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u0443 \u043d\u043e\u0434\u044b \u0441\u043e\u0441\u0435\u0434\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0443\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u0430\u044f \u043d\u043e\u0434\u0430, \u0442\u043e \u043c\u044b \u044d\u0442\u0443 \u043d\u043e\u0434\u0443 \u0441\u043d\u043e\u0432\u0430 \u0431\u0443\u0434\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c, \u0442.\u043a. \u0432\u0435\u0441\u0430 \u0434\u0435\u0442\u0435\u0439 \u043c\u043e\u0433\u0443\u0442 \u0441\u0442\u0430\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435.<\/p>\n
              \u041a\u043e\u0434:<\/p>\n<\/li>\n<\/ol>\n
              from collections import deque  graph = {     1: {2: 10, 3: 6, 4: 8},     2: {7: 11, 4: 5, 5: -4},     3: {5: 3},     4: {7: 12, 3: 2, 5: 5, 6: 7},     5: {6: 9, 9: 12},     6: {8: 8, 9: 10},     7: {6: 4, 8: 6, 9: 16},     8: {9: 15},     9: {} }  lst = deque([key for key in graph.keys()])  # \u0424\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430 parents = {}  # {\u041d\u043e\u0434\u0430: \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c} costs = {}  # \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043a \u044d\u0442\u043e\u0439 \u043d\u043e\u0434\u0435 (\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0435 \u0434\u043b\u0438\u043d\u044b \u043f\u0443\u0442\u0438 \u0434\u043e \u043d\u043e\u0434\u044b \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430) infinity = float('inf')  # \u0411\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u044c (\u043a\u043e\u0433\u0434\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u0434\u043e \u043d\u043e\u0434\u044b \u0435\u0449\u0435 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d) processed = set()  # \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043d\u043e\u0434  while lst:     node = lst.popleft()     if node not in processed:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0434\u0430 \u0443\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0435\u0435 \u0437\u0430\u043d\u043e\u0432\u043e \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c (\u0438\u043d\u0430\u0447\u0435 \u043c.\u0431. \u0431\u0435\u0441\u043a. \u0446\u0438\u043a\u043b)         for child, cost in graph[node].items():  # \u041f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0434\u0435\u0442\u044f\u043c             new_cost = cost + costs.get(node,                                         0)  # \u041f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 = \u043f\u0443\u0442\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f + \u0432\u0435\u0441 \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043d\u0435\u0442, \u0442\u043e \u043f\u0443\u0442\u044c \u0434\u043e \u043d\u0435\u0433\u043e = 0)             min_cost = costs.get(child,                                  infinity)  # \u0421\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0440\u0435\u0431\u0435\u043d\u043a\u0430 (\u0435\u0441\u043b\u0438 \u0435\u0433\u043e \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0431\u044b\u043b\u043e, \u0442\u043e \u043e\u043d \u0431\u0435\u0441\u043a.)             if new_cost < min_cost:  # \u0415\u0441\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438 \u0434\u043e \u044d\u0442\u043e\u0433\u043e,                 costs[child] = new_cost  # \u0442\u043e \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439                 parents[child] = node  # \u0422\u0430\u043a \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u0438\u043d \u043f\u0443\u0442\u044c                 if child in processed:  # \u0415\u0441\u043b\u0438 \u0440\u0435\u0431\u0435\u043d\u043e\u043a \u0431\u044b\u043b \u0432 \u0447\u0438\u0441\u043b\u0435 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445                     lst.appendleft(child)  # \u0412\u043d\u043e\u0432\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u0442\u0443 \u043d\u043e\u0434\u0443 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0435\u0433\u043e \u0437\u0430\u043d\u043e\u0432\u043e                     processed.remove(child)  # \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0438\u0437 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445         processed.add(node)  # \u041a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\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-374930","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/374930","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=374930"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/374930\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=374930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=374930"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=374930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}