[백준 1238] 파티 - JAVA

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

 

다익스트라 문제

그래프가 단방향이므로, X에 가는 경우와 갔다가 돌아오는 경우 두 번을 탐색해야 한다.

 

접근법

 

1. 돌아오는 경로 X -> ALL 탐색을 한 번 한다.

2. 가는 경로 모든N -> ALL 탐색을 N번 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

  static int N, M, X, MAX;
  static int back[];
  static List<Node>[] edge;

  static class Node implements Comparable<Node> {

    int a, v;

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

    @Override
    public int compareTo(Node n) {
      return this.v - n.v;
    }
  }

  static int[] solve(int START, int[] dis) {
    Arrays.fill(dis, MAX);
    dis[START] = 0;

    PriorityQueue<Node> q = new PriorityQueue<>();
    q.offer(new Node(START, 0));

    while (!q.isEmpty()) {
      Node n = q.poll();

      if (dis[n.a] < n.v) {
        continue;
      }

      for (Node next : edge[n.a]) {
        if (n.v + next.v < dis[next.a]) {
          dis[next.a] = n.v + next.v;
          q.offer(new Node(next.a, dis[next.a]));
        }
      }
    }

    return dis;
  }

  public static void main(String[] args) throws IOException {

    int ans = 0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    X = Integer.parseInt(st.nextToken());
    MAX = Integer.MAX_VALUE / 2;

    edge = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) {
      edge[i] = new ArrayList<>();
    }

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());

      edge[a].add(new Node(b, c));
    }

    back = new int[N + 1];
    solve(X, back);

    for (int j = 1; j <= N; j++) {
      if (j == X) {
        continue;
      }
      ans = Math.max(back[j] + solve(j, new int[N + 1])[X], ans);
    }

    System.out.println(ans);
  }
}

 

 

+ 희소 그래프인거 파악 못하고 인접행렬로 푼거 (시간 4배 차이남)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

  static int N, M, X, MAX;
  static int back[], edge[][];

  static class Node implements Comparable<Node> {

    int a, v;

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

    @Override
    public int compareTo(Node n) {
      return this.v - n.v;
    }
  }

  static int[] solve(int START, int[] dis) {
    Arrays.fill(dis, MAX);
    dis[START] = 0;

    PriorityQueue<Node> q = new PriorityQueue<>();
    q.offer(new Node(START, 0));

    while (!q.isEmpty()) {
      Node n = q.poll();

      if(dis[n.a] < n.v) continue;

      for (int to = 1; to <= N; to++) {

        if (n.v + edge[n.a][to] < dis[to]) {
          dis[to] = n.v + edge[n.a][to];
          q.offer(new Node(to, dis[to]));
        }
      }
    }

    return dis;
  }

  public static void main(String[] args) throws IOException {

    int ans = 0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    X = Integer.parseInt(st.nextToken());
    MAX = Integer.MAX_VALUE / 2;

    edge = new int[N + 1][N + 1];
    for (int i = 1; i <= N; i++) {
      Arrays.fill(edge[i], MAX);
      edge[i][i] = 0;
    }

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());

      edge[a][b] = c;
    }

    back = new int[N + 1];
    solve(X, back);

    for (int j = 1; j <= N; j++) {
      if (j == X) {
        continue;
      }
      ans = Math.max(back[j] + solve(j, new int[N + 1])[X], ans);
    }

    System.out.println(ans);
  }
}