백준 1238 - 파티 (JAVA)

 

 

1238번: 파티 (acmicpc.net)

1238번: 파티

 

각 변수 설명

n : 마을의 수
m : 마을간에 연결된 노드의 수
x : 파티가 열리는 장소의 번호
dist[] : 출발지에서 목적지까지 최단거리를 저장할 배열
list : 목적지와 그 목적지까지 가는 거리를 노드로 저장할 배열
result[] : 파티장소까지 도착하는 최소비용 + 다시 돌아오는 최소비용을 저장할 배열
           (정답출력을 위해 저장하는 최종배열)

 

 

 

풀이방법은

 

1. 목적지까지 다익스트라로 한번 돌리고, 

  - 처음 제공된 예시에서 파티가 열리는 장소는 2번 마을이므로,
    각각의 출발마을(1번, 3번, 4번)에서 2번마을까지 가는 최단거리를 구해줍니다. 

 

2. 목적지에서 돌아오는길을 역다익스트라로 한번 돌린 후 값을 더해주면 됩니다. 

  - 그 이후에 반대로 출발지를 2번으로 설정하고,
    각 마을을 도착지로 설정하여 최단거리를 구해준 뒤, 1번값과 더해준다.

 

 

 

 

import java.io.*;
import java.util.*;
 
class Node implements Comparable<Node>{
    int end, weight;
 
    public Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}
 
 
 
 
public class Main {
 
    public static int stoi(String s){return Integer.parseInt(s);}
    public static int INF = 99999999;
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static List<Node> list[];
    public static int dist[];
    public static int result[];
    public static int n,m,x;
 
    public static void main(String args[]) throws IOException {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        x = stoi(st.nextToken());
 
        dist = new int[n+1];
        list = new ArrayList[n+1];
        result = new int[n+1];
 
        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
//            result[i] = new ArrayList<>();
        }
 
        Arrays.fill(dist,INF);
 
 
        for(int i=1; i<=m; i++){
            StringTokenizer s = new StringTokenizer(br.readLine());
            int start = stoi(s.nextToken());
            int end = stoi(s.nextToken());
            int weight = stoi(s.nextToken());
            list[start].add(new Node(end,weight));
        }
 
        for(int i=1; i<=n; i++){
            Arrays.fill(dist,INF);
            daik(i);
            result[i] = dist[x]; // result[1] = 4
        }
 
        Arrays.fill(dist,INF);
        daik(x);
 
        for(int i=1; i<=n; i++){
            if(i!=x){
                result[i] += dist[i];
            }
        }
 
        int final_result = 0;
 
        for(int i=1; i<=n; i++){
            final_result = Math.max(final_result,result[i]);
        }
        System.out.println(final_result);
 
    }
 
    public static void daik(int start){
        PriorityQueue<Node> pq = new PriorityQueue();
        boolean visits[] = new boolean[n+1];
        dist[start] = 0;
        pq.add(new Node(start,0));
 
        while(!pq.isEmpty()){
            Node outNode = pq.poll();
            int out = outNode.end;
 
            if (visits[out]) continue;
            visits[out] = true;
 
            for(Node node : list[out]){
                if(dist[node.end] > dist[out] + node.weight){
                    dist[node.end] = dist[out] + node.weight;
                    pq.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }
 
 
 
}