최단경로 다익스트라 알고리즘

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
val INF = 1e9.toInt()
val num = readLine()!!.split(" ").map{it.toInt()}
val start = readLine()!!.toInt()
var graph = MutableList(num[1]+1,{ mutableListOf<Pair<Int,Int>>()})
val visited = BooleanArray(num[1]+1){false}
val distance = IntArray(num[1]+1){INF}
fun main()=with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
 
    for(i in 0 until num[1]){
        var (a,b,c) = readLine()!!.split(" ").map{it.toInt()}
        graph[a].add(Pair(b,c))
    }
    dijkstra(start)
    for(i in 1 .. num[0]){
        if(distance[i]==INF){
            println("INFINITY")
        }
        else{
            println(distance[i])
        }
    }
    bw.flush()
    bw.close()
}
 
fun get_smallest_node():Int{
    var min_value = INF
    var index = 0
    for(i in 1 .. num[0]){
        if(distance[i]<min_value && !visited[i]){
            min_value = distance[i]
            index = i
        }
    }
    return index
}
 
fun dijkstra(start:Int){
    distance[start] = 0
    visited[start] = true
    for((a,b) in graph[start]){
        distance[a]=b
    }
    for(i in 0 until num[0]-1) {
        var now = get_smallest_node()
        visited[now] = true
        for ((a, b) in graph[now]) {
            var cost = distance[now] + b
            if (cost < distance[a]) {
                distance[a] = cost
            }
        }
    }
}
 
 
 
 
 
 
 
 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
 
val br = BufferedReader(InputStreamReader(System.`in`))
val INF = 1e9.toInt()
val num = readLine()!!.split(" ").map{it.toInt()}
val start = readLine()!!.toInt()
var graph = MutableList(num[0]+1,{ mutableListOf<Pair<Int,Int>>()})
val distance = IntArray(num[0]+1){INF}
var q = PriorityQueue<Pair<Int,Int>>()
fun main()=with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    q = PriorityQueue<Pair<Int,Int>> {
        d1,d2 -> d1.first-d2.first
    }
    for(i in 0 until num[1]){
        var (a,b,c) = readLine()!!.split(" ").map{it.toInt()}
        graph[a].add(Pair(b,c))
    }
 
    dijkstra(start)
    for(i in 1 .. num[0]){
        if(distance[i]==INF){
            println("INFINITY")
        }
        else{
            println(distance[i])
        }
    }
    bw.flush()
    bw.close()
}
 
 
fun dijkstra(start:Int){
    q.add(Pair(0,start))
    distance[start] = 0
    while(!q.isEmpty()){
        var (dist,now) = q.poll()
        if(distance[now]<dist){
            continue
        }
        for((a,b) in graph[now]){
            var cost =  dist + b
            if( cost < distance[a]){
                distance[a]=cost
                q.add(Pair(cost,a))
            }
        }
    }
}