"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", blockquote: "blockquote", code: "code", h2: "h2", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", svg: "svg", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["这题很适合用来练一下 ", _jsx(_components.code, { className: "language-auto", children: "Dijkstra" }), " 算法模版。\n", _jsx(_components.a, { href: "https://leetcode.cn/problems/network-delay-time/description/", target: "_blank", rel: "noopener noreferrer", children: "743. 网络延迟时间" })] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "1-代码", children: [_jsx(_components.a, { className: "heading-link", href: "#1-代码", 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" }) }) }), "1. 代码"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c 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: "(" }), _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" }), " timesSize", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: "*" }), " timesColSize", _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: [" ", _jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " inf ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0x3f3f3f3f" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 邻接矩阵" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " used", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _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" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _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" }), " res ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "memset" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "g", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "0x3f" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "g", _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 function", children: "memset" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "0x3f" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _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 function", children: "memset" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "used", _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 keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "used", _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 operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _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"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 1. 初始化" }), "\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: "<" }), " timesSize", _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" }), " x ", _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 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 keyword", children: "int" }), " y ", _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 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: [" g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _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: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 2. 遍历n次" }), "\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" }), " j ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _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" }), " x ", _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 comment", children: "// 2.1 找最近的结点" }), "\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" }), " y ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _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: "(" }), _jsx(_components.span, { className: "token operator", children: "!" }), "used", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "&&" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "x ", _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 operator", children: "||" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _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: [" x ", _jsx(_components.span, { className: "token operator", children: "=" }), " y", _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: [" used", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" res ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "fmax" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "res", _jsx(_components.span, { className: "token punctuation", children: "," }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _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 comment", children: "// 2.2 松弛" }), "\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" }), " y ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _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: [" dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "fmin" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _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" }), " res ", _jsx(_components.span, { className: "token operator", children: "==" }), " inf ", _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 operator", children: ":" }), " res", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.h2, { id: "2-初始化", children: [_jsx(_components.a, { className: "heading-link", href: "#2-初始化", 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" }) }) }), "2. 初始化"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " inf ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0x3f3f3f3f" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 维护邻接矩阵" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 最短路径数组" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " used", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 标志是否最短" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "k ", _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 operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 从k开始出发" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ans ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 全局答案" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token function", children: "memset" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "g", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "0x3f" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "g", _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 comment", children: "// 全部设置为infty" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token function", children: "memset" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "0x3f" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _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 comment", children: "// 最开始最短路径全部初始化为 infty" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token function", children: "memset" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "used", _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 keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "used", _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 comment", children: "// 标记哪些点已经确定的最短路径" }), "\n"] }), _jsx(_components.span, { className: "code-line", 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: "<" }), " timesSize", _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: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 遍历每一条边" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["\t", _jsx(_components.span, { className: "token keyword", children: "int" }), " x ", _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 operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " y ", _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 operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// x 为入边，y 表示出边" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["\tg", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _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: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// x->y的权值" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsx(_components.p, { children: "维护的变量如下：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "inf" }), "：表示无穷大的 ", _jsx(_components.code, { className: "language-auto", children: "int" }), " 值。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "g" }), "：邻接矩阵，初始化为 all ", _jsx(_components.code, { className: "language-auto", children: "inf" }), "，后续通过题目给的数据进行初始化。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "dist" }), "：k 到结点 ", _jsx(_components.code, { className: "language-auto", children: "i" }), " 最短路径，初始化为 ", _jsx(_components.code, { className: "language-auto", children: "inf" }), "，最后一位置为 ", _jsx(_components.code, { className: "language-auto", 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: "k" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "k-1" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7778em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0315em" }, children: "k" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] })] }), " 为第 ", _jsx(_components.code, { className: "language-auto", children: "k" }), " 个结点，默认置为 ", _jsx(_components.code, { className: "language-auto", children: "0" }), "。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "used" }), "：标记结点是否被使用过，用于后续寻找迭代的接力结点。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "ans" }), "：全局答案。"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["注意 ", _jsx(_components.code, { className: "language-auto", children: "0x3f3f3f3f" }), " 是一个十进制，四个字节。而 ", _jsx(_components.code, { className: "language-auto", children: "memset()" }), " 函数按照字节为单位作为填充，所以后面的 ", _jsx(_components.code, { className: "language-auto", children: "memset()" }), " 中为 ", _jsx(_components.code, { className: "language-auto", children: "0x3f" }), "，而非 ", _jsx(_components.code, { className: "language-auto", children: "0x3f3f3f3f" }), "。"] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "3-主循环", children: [_jsx(_components.a, { className: "heading-link", href: "#3-主循环", 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" }) }) }), "3. 主循环"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_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: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token operator", children: "++" }), "i", _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" }), " x ", _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 keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " y ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _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 comment", children: "// 遍历所有的结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "!" }), "used", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "&&" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "x ", _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 operator", children: "||" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _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 comment", children: "// 未使用 || (第一次 && y更短)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" x ", _jsx(_components.span, { className: "token operator", children: "=" }), " y", _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: [" used", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ans ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "fmax" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "ans", _jsx(_components.span, { className: "token punctuation", children: "," }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _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 comment", 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" }), " y ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _jsx(_components.span, { className: "token operator", children: "<" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " y ", _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: [" dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "fmin" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " dist", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " g", _jsx(_components.span, { className: "token punctuation", children: "[" }), "x", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "y", _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 comment", 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" }), " ans ", _jsx(_components.span, { className: "token operator", children: "==" }), " inf ", _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 operator", children: ":" }), " ans", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.ul, { 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: "n" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" })] }) })] }), " 次。"] }), "\n", _jsxs(_components.li, { children: ["内次第一次循环：遍历所有节点，嗅探最近的不确定结点，将 ", _jsx(_components.code, { className: "language-auto", children: "x" }), " 标记为已更新。"] }), "\n", _jsxs(_components.li, { children: ["内层第二次循环：松弛 ", _jsx(_components.code, { className: "language-auto", children: "x" }), " 与其他所有结点。"] }), "\n"] })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };