백준 14618번
https://www.acmicpc.net/problem/14618
다익스트라 문제이다.
고생을 꽤나 해서 풀었는데, N
과 M
을 반복에서 잘못사용해서 생긴 문제였다..
N
과 M
이 헷갈려도 틀리지 않는 테스트케이스였음...문제는 사실상 어렵지 않았다.
dist
배열에 들어가있는 값중 가장 낮은 값을 선택하면 되는 문제였다
import java.io.*
import java.util.*
// input
private lateinit var br: BufferedReader
// variables
private const val INF = Int.MAX_VALUE
private var N = 0
private var M = 0
private var J = 0
private var K = 0
private lateinit var houseTypeA: IntArray
private lateinit var houseTypeB: IntArray
private lateinit var adjList: MutableList<MutableList<Node>>
private lateinit var dist: IntArray
private data class Node(var num: Int, var weight: Int)
fun main() {
br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
input()
dijkstra(J)
var aMin = INF
var bMin = INF
houseTypeA.forEach { houseNum ->
val d = dist[houseNum]
aMin = Math.min(aMin, d)
}
houseTypeB.forEach { houseNum ->
val d = dist[houseNum]
bMin = Math.min(bMin, d)
}
// A형 집과 B형 집의 거리가 같으면 A형의 집에 산다
if (aMin == INF && bMin == INF) {
sb.append(-1)
} else {
if (aMin <= bMin) {
sb.append('A').append('\n').append(aMin)
} else {
sb.append('B').append('\n').append(bMin)
}
}
bw.write(sb.toString())
bw.close()
} // End of main
private fun dijkstra(startNodeNum: Int) {
val comp = Comparator<Node> { o1, o2 -> o1.weight - o2.weight }
val pque = PriorityQueue(comp)
val isVisited = BooleanArray(N + 1)
pque.offer(Node(startNodeNum, 0))
dist[startNodeNum] = 0
for (i in generateSequence { }) {
if (pque.isEmpty()) break
val pollNode = pque.poll()
if (isVisited[pollNode.num]) continue
isVisited[pollNode.num] = true
adjList[pollNode.num].forEach { nextNode ->
val nextNum = nextNode.num
val nextWeight = nextNode.weight
if (dist[nextNum] > nextWeight + dist[pollNode.num]) {
dist[nextNum] = nextWeight + dist[pollNode.num]
pque.offer(Node(nextNum, dist[nextNum]))
}
}
}
} // End of dijkstra
private fun input() {
var st = StringTokenizer(br.readLine())
N = st.nextToken().toInt() // 집의 수
M = st.nextToken().toInt() // 집과 집 사이의 도로 수
J = br.readLine().toInt() // 진서의 집
K = br.readLine().toInt() // 종류별 동물의 수
houseTypeA = IntArray(K) // A 형의 집
houseTypeB = IntArray(K) // B 형의 집
st = StringTokenizer(br.readLine())
for (i in 0 until K) {
houseTypeA[i] = st.nextToken().toInt()
}
st = StringTokenizer(br.readLine())
for (i in 0 until K) {
houseTypeB[i] = st.nextToken().toInt()
}
adjList = ArrayList()
repeat(N + 1) {
adjList.add(ArrayList())
}
dist = IntArray(N + 1) { INF }
for (i in 0 until M) {
st = StringTokenizer(br.readLine())
val x = st.nextToken().toInt()
val y = st.nextToken().toInt()
val z = st.nextToken().toInt()
adjList[x].add(Node(y, z))
adjList[y].add(Node(x, z))
}
} // End of input