해당 문제는 간선의 가중치가 0 이상이고, 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 문제이기 때문에, 다익스트라 알고리즘을 사용하면 될 것 같았다. 단, 조건이 하나 붙게 되는데 주어진 두 정점을 반드시 거쳐야 하는 정점 번호가 주어진다.


1번 노드로 시작했을 때 최단경로, v1 노드로 시작했을 때 최단 경로, v2로 시작했을 때 최단 경로를 각각 구해주면 된다.
v1을 먼저 방문하는 경로와 v2를 먼저 방문하는 경로가 있을 수 있는데 둘 중 더 작은 값이 나오는 걸로 결과를 도출하면 된다.
코드
(function main() {
const fs = require("fs");
const isLocal = true;
const filePath = isLocal ? "t.txt" : "/dev/stdin";
const input = fs.readFileSync(filePath).toString().trim().split('\n');
class MinHeap {
constructor() {
this.items = []
}
size() {
return this.items.length
}
pop() {
if (this.size() === 0) {
return
}
const min = this.items[0]
this.items[0] = this.items[this.size() - 1]
this.items.pop()
this.bubbleDown()
return min
}
push(item) {
this.items.push(item)
this.bubbleUp()
}
swap(a, b) {
[this.items[a], this.items[b]] = [this.items[b], this.items[a]]
}
bubbleUp() {
let index = this.size() - 1
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2)
if (this.items[parentIndex][0] < this.items[index][0]) {
break
}
this.swap(index, parentIndex)
index = parentIndex
}
}
bubbleDown() {
let index = 0
while (index * 2 + 1 < this.size()) {
let leftChild = index * 2 + 1
let rightChild = index * 2 + 2
let smallerChild = rightChild < this.size() && this.items[rightChild][0] < this.items[leftChild][0] ? rightChild : leftChild
if (this.items[index][0] < this.items[smallerChild][0]) {
break
}
this.swap(index, smallerChild)
index = smallerChild
}
}
}
const [N, E] = input[0].split(' ').map(Number)
const graph = Array.from({ length: N + 1 }, () => [])
const required = input[input.length - 1].split(' ').map(Number)
console.log(required)
for (let i = 1; i < input.length - 1; i++) {
const [a, b, c] = input[i].split(' ').map(Number)
graph[a].push([b, c])
graph[b].push([a, c])
}
function dijkstra(start) {
const dist = Array.from({ length: N + 1 }, () => Infinity)
const pq = new MinHeap()
pq.push([0, start])
dist[start] = 0
while (pq.size() > 0) {
const [curDist, curNode] = pq.pop()
if (curDist > dist[curNode]) {
continue
}
for (let [adjNode, adjDist] of graph[curNode]) {
const newDist = curDist + adjDist
if (dist[adjNode] > newDist) {
pq.push([newDist, adjNode])
dist[adjNode] = newDist
}
}
}
return dist
}
const distFrom1 = dijkstra(1)
const distFromV1 = dijkstra(required[0])
const distFromV2 = dijkstra(required[1])
const case1 = distFrom1[required[0]] + distFromV1[required[1]] + distFromV2[N]
const case2 = distFrom1[required[1]] + distFromV2[required[0]] + distFromV1[N]
const result = Math.min(case1, case2)
console.log(result >= Infinity ? -1 : result)
})();