"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", figure: "figure", h2: "h2", img: "img", li: "li", math: "math", mi: "mi", mo: "mo", mrow: "mrow", ol: "ol", p: "p", pre: "pre", semantics: "semantics", span: "span", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: _jsx(_components.a, { href: "https://www.acmicpc.net/problem/2307", children: "문제 링크" }) }), "\n", _jsx(_components.h2, { children: "문제" }), "\n", _jsx(_components.p, { children: "그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-2307/assets/img1.png", alt: "" }) }), "\n", _jsx(_components.p, { children: "그림 1" }), "\n", _jsx(_components.p, { children: "예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다." }), "\n", _jsx(_components.p, { children: "어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하려고 한다. 따라서 용의자는 이 도로를 피해서 가장 빠르게 도시를 탈출하고자 한다. 이 경우 경찰이 검문을 위하여 선택하는 도로에 따라서 용의자의 가장 빠른 탈출시간은 검문이 없을 때에 비하여 더 늘어날 수 있다." }), "\n", _jsx(_components.p, { children: "문제는 도로검문을 통하여 얻을 수 있는 탈출의 최대 지연시간을 계산하는 것이다. 추가설명은 다음과 같다." }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "두 개의 지점을 직접 연결하는 도로가 있는 경우, 그 도로는 유일하다." }), "\n", _jsx(_components.li, { children: "도시의 지점(노드)은 1에서 N번까지 N개의 연속된 정수로 표시된다." }), "\n", _jsx(_components.li, { children: "용의자가 도시에 진입하는 지점은 항상 1번이고 도시를 빠져 나가기 위하여 최종적으로 도달해야하는 지점은 항상 N번 지점이다." }), "\n", _jsx(_components.li, { children: "용의자는 검문을 피해서 가장 빨리 도시를 빠져나가고자 하고, 경찰은 적절한 도로를 선택하여 이 용이자들의 탈출시간을 최대한 지연시키고자 한다." }), "\n", _jsx(_components.li, { children: "각 도시 지점 간을 이동하는 시간은 항상 양의 정수이다." }), "\n"] }), "\n", _jsx(_components.p, { children: "입력 도시의 도로망에 따라서 경찰이 어떤 도로를 막으면 용의자는 도시를 탈출하지 못할 수도 있다. 이 경우 검문으로 인하여 지연시킬 수 있는 탈출시간은 무한대이다. 이 경우에는 -1을 출력해야 한다." }), "\n", _jsx(_components.p, { children: "그림 1에서 볼 때 검문이 없을 경우 용의자가 도시를 탈출하는데 걸리는 시간은 4분이다. 만일 경찰이 도로(4,3)을 막으면 그 탈출시간을 지연시킬 수 없으므로 지연시간은 0이다. 만일 도로(2,3)을 막으면, 용의자들이 가장 빠르게 탈출할 수 있는 시간은 5분이므로 탈출지연시간은 1분이고, 도로(3,6)을 막으면 탈출지연시간은 2분이다." }), "\n", _jsx(_components.p, { children: "여러분은 입력 데이터에 표시된 도로망을 읽고, 경찰이 한 도로를 막고 검문함으로써 지연시킬 수 있는 최대시간을 정수로 출력하여야한다. 만일 지연효과가 없으면 0을 출력해야하고, 도시를 빠져나가지 못하게 만들 수 있으면(지연시간이 무한대) -1을 출력해야 한다." }), "\n", _jsx(_components.h2, { children: "입력" }), "\n", _jsx(_components.p, { children: "첫 줄에는 지점의 수를 나타내는 정수 N(6 <= N <= 1000)과 도로의 수 M(6 <= M <= 5000)이 주어진다. 그 다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 <= t <= 10000이다.

" }), "\n", _jsx(_components.h2, { children: "출력" }), "\n", _jsx(_components.p, { children: "경찰이 하나의 도로를 막음으로써 지연시킬 수 있는 최대 시간을 정수로 출력한다. (단, 그 지연시간이 무한대이면 -1을 출력해야 한다.)" }), "\n", _jsx(_components.h2, { children: "풀이" }), "\n", _jsx(_components.p, { children: "모든 도로를 하나씩 막아 보며 다익스트라를 돌리면 맞긴 하지만, 꼭 그럴 필요는 없다. 실제로 영향을 줄 수 있는 도로는 처음 최단 경로 위에 있는 간선들뿐이다." }), "\n", _jsxs(_components.p, { children: ["코드에서는 먼저 다익스트라를 한 번 실행해 원래 최단 거리와 함께 ", _jsx(_components.code, { children: "parent[]" }), "를 저장한다. 이 ", _jsx(_components.code, { children: "parent[]" }), "는 최단 경로 트리를 따라 ", _jsx(_components.code, { children: "N" }), "에서 1로 되짚어 올라갈 수 있게 해준다."] }), "\n", _jsxs(_components.p, { children: ["그 다음에는 원래 최단 경로에 포함된 간선만 하나씩 막아 가며 다시 다익스트라를 실행한다. 어떤 간선을 막았는데도 다른 우회 경로가 있으면 지연 시간을 갱신하고, 아예 도달할 수 없으면 답은 곧바로 ", _jsx(_components.code, { children: "-1" }), "이다."] }), "\n", _jsx(_components.p, { children: "핵심은 \"최단 경로에 없던 간선을 막아도 원래 최단 시간은 변하지 않는다\"는 점이다. 그래서 첫 최단 경로를 역추적한 뒤 그 위의 간선만 검사해도 충분하다." }), "\n", _jsx(_components.h2, { children: "코드" }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { style: { backgroundColor: "#2e3440ff", color: "#d8dee9ff" }, tabIndex: "0", "data-language": "java", "data-theme": "nord", children: _jsxs(_components.code, { "data-language": "java", "data-theme": "nord", style: { display: "grid" }, children: [_jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "import" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " java" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "util" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "*;" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "import" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " java" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "io" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "*;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "public" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " class" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " Main" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " class" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " Node" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " implements" }), _jsx(_components.span, { style: { color: "#8FBCBB", fontWeight: "bold" }, children: " Comparable" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " public" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " this" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " this" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#ECEFF4" }, children: " @" }), _jsx(_components.span, { style: { color: "#D08770" }, children: "Override" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " public" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " compareTo" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Node" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " o" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "compare" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "this" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " o" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayList" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " graph" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " parent" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " public" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " void" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " main" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "String" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " args" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " throws" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " IOException" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " BufferedReader" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " br" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " BufferedReader" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " InputStreamReader" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "System" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "in" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " StringTokenizer" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " st" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " StringTokenizer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "br" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "readLine" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " N" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " M" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " parent " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " graph " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayList" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " N" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " graph" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "i" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayList" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<>()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "M" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "--" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " >" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " st " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " StringTokenizer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "br" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "readLine" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " a" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " b" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " t" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " graph" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "a" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "add" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "b" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " t" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " graph" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "b" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "add" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "a" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " t" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " N" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Collections" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "sort" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "graph" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "i" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "])" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " originalMinTIme" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " -" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " -" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " curNode" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " N" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " maxDelay" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "curNode " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "!=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " prevNode" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " parent" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "curNode" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " blockedTime" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " prevNode" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " curNode" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "blockedTime " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "==" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "MAX_VALUE" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " System" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "out" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "println" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "-" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#81A1C1" }, children: " return;" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " maxDelay " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Math" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "max" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "maxDelay" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " blockedTime " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "-" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " originalMinTIme" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " curNode " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " prevNode" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " System" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "out" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "println" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "maxDelay" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " N" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " blockA" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " blockB" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " dist" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Arrays" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "fill" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "MAX_VALUE" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " PriorityQueue" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " pq" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " PriorityQueue" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<>()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " pq" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "offer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "!" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "pq" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "isEmpty" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " Node" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cur" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " pq" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "poll" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " <" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " continue;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Node" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " next" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " :" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " graph" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "])" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " ((" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " ==" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " blockA " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "&&" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " ==" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " blockB" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " ||" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " ==" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " blockB " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "&&" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " ==" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " blockA" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#81A1C1" }, children: " continue;" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " >" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " pq" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "offer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " Node" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "blockA " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "==" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " -" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " parent" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "end" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dist" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) })] }) }) }), "\n", _jsx(_components.h2, { children: "복잡도" }), "\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: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "P" }), _jsx(_components.mo, { children: "⋅" }), _jsx(_components.mi, { children: "M" }), _jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" }), _jsx(_components.mi, { children: "N" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(P \\cdot M \\log N)" })] }) }) }), _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", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "P" }), _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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "P" }), "는 원래 최단 경로에 포함된 간선 수"] }), "\n"] }), "\n"] }), "\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: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "N" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "M" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(N + M)" })] }) }) }), _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", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _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: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n"] }), "\n", _jsx(_components.h2, { children: "마무리" }), "\n", _jsx(_components.p, { children: "핵심은 모든 도로를 막아보는 게 아니라, 처음 최단 경로를 만든 도로들만 다시 보는 것이다. 최단 경로 계산과 역추적을 연결하면 브루트포스를 꽤 많이 줄일 수 있다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-2307/assets/1.png", alt: "" }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };

BOJ 2307 - 도로검문