최단경로 1753

LJM·2023년 3월 7일
0

백준풀기

목록 보기
131/259

https://www.acmicpc.net/problem/1753

import java.io.*;
import java.util.*;

class Node implements Comparable<Node>
{
    int v;
    int w;

    public Node() {
    }

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return this.w < o.w ? -1 : 1 ;
    }
}

public class Main
{
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();

    static PriorityQueue<Node> queue = new PriorityQueue();
    static int V;
    static int E;
    static int K;

    static int[] dis;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        V = Integer.parseInt(input[0]);
        E = Integer.parseInt(input[1]);
        K = Integer.parseInt(br.readLine());

        dis = new int[V+1];
        Arrays.fill(dis, Integer.MAX_VALUE);

        for(int i = 0; i < V+1; ++i)
            graph.add(new ArrayList<>());

        for(int i = 0; i < E; ++i)
        {
            input = br.readLine().split(" ");

            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            int w = Integer.parseInt(input[2]);

            graph.get(u).add(new Node(v, w));
        }

        queue.add(new Node(K, 0));
        dis[K] = 0;

        while(queue.isEmpty() == false)
        {
            Node curNode = queue.poll();
            if(curNode.w > dis[curNode.v])
               continue;

            ArrayList<Node> adjList = graph.get(curNode.v);
            for(int i = 0; i < adjList.size(); ++i)
            {
                Node adj = adjList.get(i);

                int cost = dis[curNode.v] + adj.w;
                if( cost <= dis[adj.v])
                {
                    queue.add(new Node(adj.v, cost));
                    dis[adj.v] = cost;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < V+1; ++i)
        {
            if( dis[i] == Integer.MAX_VALUE)
                sb.append("INF\n");
            else
                sb.append(dis[i] + "\n");
        }

        System.out.println(sb);

    }
}
profile
게임개발자 백엔드개발자

0개의 댓글