[Javascript][BOJ] 1238 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

핵심아이디어

다익스트라로 풀되, 각 지점을 모두 start로 지정하고 다익스트라를 수행한 뒤,

start -> X + X -> start 가 가장 max인 거리를 찾으면된다.

python에서는 우선순위 큐로 heap을 썼지만, 자바스크립트에는 해당기능이 없어서 일반 큐로 구현하였는데,

간당간당하게 통과했다!

다익스트라용 우선순위큐를 만들어놓아야 할 것 같다..

 

'use strict';

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

const allDistances = {};

const dijkstra = (n, start, graph) => {
	const distance = Array.from({ length: n + 1 }, () => Infinity);
	const q = [];
	distance[start] = 0;
	q.push([start, 0]);

	while (q.length>0) {
		const [curr, weight] = q.shift();
		for (const [dest, cost] of graph[curr]) {
				if (distance[dest] > weight + cost) {
                    distance[dest] = weight + cost;
					q.push([dest,distance[dest]]);
				}
		}
	}
	allDistances[start] = distance;
};

const solution = function (input) {
	const [n, m, x] = input
		.shift()
		.split(' ')
		.map((e) => parseInt(e));
	const graph = {};
	let answer = 0;
	for (let i = 1; i <= n; i++) {
		graph[i] = [];
	}
	for (const row of input) {
		const [a, b, c] = row.split(' ').map((e) => parseInt(e));
		graph[a].push([b, c]);
	}
	for (let start = 1; start <= n; start++) {
		dijkstra(n, start, graph);
	}
	for (let start = 1; start <= n; start++) {
		answer = Math.max(answer, allDistances[start][x] + allDistances[x][start]);
	}
	console.log(answer);
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});