"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", code: "code", em: "em", h3: "h3", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", msup: "msup", ol: "ol", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", strong: "strong", svg: "svg", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: _jsx(_components.a, { href: "https://zhuanlan.zhihu.com/p/96621396", target: "_blank", rel: "noopener noreferrer", children: "算法学习笔记(6)：最短路问题 - 知乎" }) }), "\n", _jsx(_components.p, { children: "算法过程：" }), "\n", _jsxs(_components.p, { children: ["将结点分成两个集合：已确定最短路长度的点集（记为", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "S" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "S" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0576em" }, children: "S" })] }) })] }), "集合）的和未确定最短路长度的点集（记为", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "T" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" })] }) })] }), "集合）。一开始所有的点都属于", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "T" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" })] }) })] }), "集合。"] }), "\n", _jsxs(_components.p, { children: ["初始化", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "d" }), _jsx(_components.mi, { children: "i" }), _jsx(_components.mi, { children: "s" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "s" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "dis(s)=0" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "d" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mord mathnormal", children: "s" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "s" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "0" })] })] })] }), "，其他点的", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "d" }), _jsx(_components.mi, { children: "i" }), _jsx(_components.mi, { children: "s" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "dis" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "d" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mord mathnormal", children: "s" })] }) })] }), "均为", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { mathvariant: "normal", children: "∞" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "+\\infty" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6667em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "+" }), _jsx(_components.span, { className: "mord", children: "∞" })] }) })] }), "。"] }), "\n", _jsx(_components.p, { children: "然后重复这些操作：" }), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["从", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "T" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" })] }) })] }), "集合中，选取一个最短路长度最小的结点，移到", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "S" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "S" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0576em" }, children: "S" })] }) })] }), "集合中。"] }), "\n", _jsxs(_components.li, { children: ["对那些刚刚被加入", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "S" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "S" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0576em" }, children: "S" })] }) })] }), "集合的结点的所有出边执行松弛操作。"] }), "\n"] }), "\n", _jsxs(_components.p, { children: ["直到", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "T" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" })] }) })] }), "集合为空，算法结束。"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Time Complexity" }), ": ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(n^2)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n", _jsxs(_components.h3, { id: "example-0", children: [_jsx(_components.a, { className: "heading-link", href: "#example-0", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "Example 0:"] }), "\n", _jsx(_components.p, { children: _jsx(_components.a, { href: "https://leetcode.com/problems/network-delay-time/", target: "_blank", rel: "noopener noreferrer", children: "743. Network Delay Time" }) }), "\n", _jsxs(_components.p, { children: ["You are given a network of ", _jsx(_components.code, { className: "language-auto", children: "n" }), " nodes, labeled from ", _jsx(_components.code, { className: "language-auto", children: "1" }), " to ", _jsx(_components.code, { className: "language-auto", children: "n" }), ". You are also given ", _jsx(_components.code, { className: "language-auto", children: "times" }), ", a list of travel times as directed edges ", _jsx(_components.code, { className: "language-auto", children: "times[i] = (ui, vi, wi)" }), ", where ", _jsx(_components.code, { className: "language-auto", children: "ui" }), " is the source node, ", _jsx(_components.code, { className: "language-auto", children: "vi" }), " is the target node, and ", _jsx(_components.code, { className: "language-auto", children: "wi" }), " is the time it takes for a signal to travel from source to target."] }), "\n", _jsxs(_components.p, { children: ["We will send a signal from a given node ", _jsx(_components.code, { className: "language-auto", children: "k" }), ". Return ", _jsxs(_components.em, { children: ["the ", _jsx(_components.strong, { children: "minimum" }), " time it takes for all the"] }), " ", _jsx(_components.code, { className: "language-auto", children: "n" }), " ", _jsx(_components.em, { children: "nodes to receive the signal" }), ". If it is impossible for all the ", _jsx(_components.code, { className: "language-auto", children: "n" }), " nodes to receive the signal, return ", _jsx(_components.code, { className: "language-auto", children: "-1" }), "."] }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "networkDelayTime" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">>" }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "times", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " k", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" vector", _jsx(_components.span, { className: "token operator", children: "<" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), "Edge", _jsx(_components.span, { className: "token operator", children: ">>" }), " ", _jsx(_components.span, { className: "token function", children: "g" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " times", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " u ", _jsx(_components.span, { className: "token operator", children: "=" }), " times", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " v ", _jsx(_components.span, { className: "token operator", children: "=" }), " times", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " w ", _jsx(_components.span, { className: "token operator", children: "=" }), " times", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "u", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "push_back" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "v", _jsx(_components.span, { className: "token punctuation", children: "," }), " w", _jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " ", _jsx(_components.span, { className: "token function", children: "dist" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " INT_MAX", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "bool" }), _jsx(_components.span, { className: "token operator", children: ">" }), " ", _jsx(_components.span, { className: "token function", children: "visited" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token boolean", children: "false" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "auto" }), " cmp ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "const" }), " Edge ", _jsx(_components.span, { className: "token operator", children: "&" }), "a", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "const" }), " Edge ", _jsx(_components.span, { className: "token operator", children: "&" }), "b", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " a", _jsx(_components.span, { className: "token punctuation", children: "." }), "second ", _jsx(_components.span, { className: "token operator", children: ">" }), " b", _jsx(_components.span, { className: "token punctuation", children: "." }), "second", _jsx(_components.span, { className: "token punctuation", children: ";" }), _jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" priority_queue", _jsx(_components.span, { className: "token operator", children: "<" }), "Edge", _jsx(_components.span, { className: "token punctuation", children: "," }), " vector", _jsx(_components.span, { className: "token operator", children: "<" }), "Edge", _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "decltype" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cmp", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: ">" }), " ", _jsx(_components.span, { className: "token function", children: "pq" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cmp", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" pq", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "push" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "k", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "k", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "!" }), "pq", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "empty" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "auto" }), " ", _jsx(_components.span, { className: "token punctuation", children: "[" }), "u", _jsx(_components.span, { className: "token punctuation", children: "," }), " du", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " pq", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "top" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" pq", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "pop" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "visited", _jsx(_components.span, { className: "token punctuation", children: "[" }), "u", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "continue" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" visited", _jsx(_components.span, { className: "token punctuation", children: "[" }), "u", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token boolean", children: "true" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "auto" }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "e ", _jsx(_components.span, { className: "token operator", children: ":" }), " g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "u", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "auto" }), " ", _jsx(_components.span, { className: "token punctuation", children: "[" }), "v", _jsx(_components.span, { className: "token punctuation", children: "," }), " w", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " e", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "du ", _jsx(_components.span, { className: "token operator", children: "+" }), " w ", _jsx(_components.span, { className: "token operator", children: "<" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "v", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "v", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " du ", _jsx(_components.span, { className: "token operator", children: "+" }), " w", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" pq", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "push" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "v", _jsx(_components.span, { className: "token punctuation", children: "," }), " du ", _jsx(_components.span, { className: "token operator", children: "+" }), " w", _jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " cnt ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " maxd ", _jsx(_components.span, { className: "token operator", children: "=" }), " INT_MIN", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<=" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " i", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "!=" }), " INT_MAX", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cnt", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" maxd ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "maxd", _jsx(_components.span, { className: "token punctuation", children: "," }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " cnt ", _jsx(_components.span, { className: "token operator", children: "==" }), " n ", _jsx(_components.span, { className: "token operator", children: "?" }), " maxd ", _jsx(_components.span, { className: "token operator", children: ":" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };

Links to this page: