백준 1238번 : 파티

1. 문제 설명 (1238)

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

2. 분류

• Dijkstra
  
  

3. 풀이

(1753)번 문제와 거의 같다. 단방향 간선들이 존재하고, 단순히 X 번 정점을 방문하고 돌아오면 끝이다. 역시 Dijkstra 알고리즘을 활용한 문제이다.

따라서 LinkedList 와 PriorityQueue 를 활용해 그래프를 구현하고, Node 클래스를 정의했다. 1753번 문제와는 다르게 경로가 항상 존재하므로, 경로가 없는 경우는 고려하지 않았다.

풀고 나서 생각해보니 dp를 활용하면 dijkstra 알고리즘을 M번이나 반복할 필요가 없어보인다. 하지만 이미 풀었으므로 패스.

4. 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

import java.io.*; import java.util.*;   public class Q1238 {       static LinkedList<Node> list[];     static int distance[];     static int N, M, X;          public static void main(String args[]) throws Exception{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         String[] nmx = br.readLine().split(" ");         N = Integer.parseInt(nmx[0]);         M = Integer.parseInt(nmx[1]);         X = Integer.parseInt(nmx[2]);         list = new LinkedList[N+1];         distance = new int[N+1];         for(int i = 1; i <= N; i++)             list[i] = new LinkedList<>();                  for(int i = 0; i < M; i++) {             String[] grp = br.readLine().split(" ");             int n1 = Integer.parseInt(grp[0]);             int n2 = Integer.parseInt(grp[1]);             int c = Integer.parseInt(grp[2]);             list[n1].add(new Node(n2, c));         }                  int[] answer = new int[N+1];                  for(int i = 1; i <= N; i++) {             answer[i] += dijkstra(i, X);             answer[i] += dijkstra(X, i);         }                  Arrays.sort(answer);         bw.write(answer[N]+"");         bw.flush();         bw.close();     }          public static int dijkstra(int start, int end) {         distance = new int[N+1];         Arrays.fill(distance, Integer.MAX_VALUE);         distance[start] = 0;         PriorityQueue<Node> pq = new PriorityQueue<>();         pq.add(new Node(start, 0));                  while(!pq.isEmpty()) {             Node now = pq.poll();             int number = now.number;             int weight = now.weight;             if(distance[number] < weight)                 continue;                          for(int i = 0; i < list[number].size(); i++) {                 int number2 = list[number].get(i).number;                 int weight2 = list[number].get(i).weight + weight;                 if(distance[number2] > weight2) {                     distance[number2] = weight2;                     pq.add(new Node(number2, weight2));                 }             }         }         return distance[end];     }          static class Node implements Comparable<Node> {         int number, weight;                  Node(int n, int w) {             this.number = n;             this.weight = w;         }                  @Override         public int compareTo(Node n) {             return weight - n.weight;         }     }      } Colored by Color Scripter

cs

5. 결과

984ms로 잘 작동한다.