파티

• https://www.acmicpc.net/problem/1238

문제풀이

자바스크립트는 heap으로 구현된 우선순위큐가 없으므로 구현해주면 좋다..

다익스트라를 이용해서 풀 수 있는 문제이다. 두 번 다익스트라를 사용해서 최단 거리를 구해야하는데, X에서 각 도시로 가는길과, X에서 역방향으로 도시로 가는 길 이 두 가지를 구해야한다.

1. 주어진 도로에 대해서 단방향으로 진행할 수 있는 인접리스트를 만들고, 역방향으로 진행할 수 있는 인접리스트를 만든다.
2. 각 인접리스트로 다익스트라를 돌리고, distance 배열에서 최댓값을 뽑아주면 된다.

소스코드

const log = console.log;
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

class Heap { /* 구현 내용은 생략 */ }

const [N, M, X] = input[0].split(" ").map(e => +e);
let doro = input.slice(1, 1+M).map(e => e.split(" ").map(el => +el));
const doro2 = doro.reduce((arr, val) => {
  const [start, end , cost] = val;
  arr[end] ? arr[end].push([start, cost]) : arr[end] = [[start, cost]];
  return arr;
}, []);
doro = doro.reduce((arr, val) => {
  const [start, end, cost] = val;
  arr[start] ? arr[start].push([end, cost]) : arr[start] = [[end, cost]]; 
  return arr;
}, []);

const distance = Array(N+1).fill(Infinity);
const visited = Array(N+1).fill(false);
const queue = new Heap();

queue.push([X, 0]);
distance[X] = 0;

while(queue.size()){
  const [start, cost] = queue.shift();
  visited[start] = true;
  for(let i=0 ; i<doro[start].length ; i++){
    const [v, c] = doro[start][i];
    if(visited[v]) continue;
    if(distance[v] > cost + c){
      distance[v]  = cost + c;
      queue.push([v, cost+c]);
    }
  }
}

const distance2 = Array(N+1).fill(Infinity);
const visited2 = Array(N+1).fill(false);
const queue2 = new Heap();

queue2.push([X, 0]);

distance2[X] = 0;

while(queue2.size()){
  const [start, cost] = queue2.shift();
  visited2[start] = true;
  for(let i=0 ; i<doro2[start].length ; i++){
    const [v, c] = doro2[start][i];
    if(visited2[v]) continue;
    if(distance2[v] > cost + c){
      distance2[v]  = cost + c;
      queue2.push([v, cost+c]);
    }
  }
}

let max = 0;
for(let i=1 ; i<distance.length ; i++){
  let result = distance[i] + distance2[i];
  if(max < result){
    max = result;
  }
}

log(max);