문제
https://www.acmicpc.net/problem/1238
풀이
N개의 숫자로 구분된 마을에 한 명씩 학생이 살고 있다.N명의 학생이X번 마을에 모여서 파티를 벌이기로 했다.- 마을 사이에는
M개의 단방향 도로들이 있고i번째 길을 지나는데Ti의 시간을 소비한다. - 파티에 참석하기 위해 걸어가서 다시 자신의 마을로 최단 시간을 소비해 돌아와야 한다.
N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생을 출력하라.
Dijkstra(다익스트라) 문제
각 마을의 학생들이 갈 수 있는 도로를 통해 X번에 도착한 후, X번 마을에서 다시 자신들의 마을로 돌아오는 최단 경로를 구하는 문제입니다.
입력
public static void main(String[] args) throws IOException {
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());
map = new ArrayList<>();
rev = new ArrayList<>();
for (int i = 0; i <= n; i++) {
map.add(new ArrayList<>());
rev.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
map.get(u).add(new Node(v, w));
rev.get(v).add(new Node(u, w));
}- 각자의 마을에서
X로 가는 최단 경로와X에서 다시 마을로 돌아오는 배열을 각각 만들어 줍니다. - 가중치를 입력 받을 때, 가는 경로와 돌아오는 경로를 각각 넣어 줍니다.
static class Node implements Comparable<Node> {
int idx, cost;
Node (int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}- 도착지, 가중치의 값을 관리하기 위한 클래스입니다.
최단 경로 탐색
private static int[] dijkstra(List<ArrayList<Node>> g, int start) {
int[] dist = new int[n+1]; // 각 점까지의 거리
Arrays.fill(dist, INF); // 최단 경로를 찾기 위해 최댓값으로 초기화
dist[start] = 0; // 시작 지점은 0
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0)); // 시작 노드, 이동거리 0
while (!pq.isEmpty()) {
Node cur = pq.poll();
int u = cur.idx; // 큐에서 뽑은 시작 노드
int d = cur.cost; // 노드에 대한 이동거리
if (dist[u] < d) continue; // 만약 큐에서 나온 노드까지의 거리가 d보다 짧다면 탐색은 하지 않아도 됨
// 인접 노드 탐색
for (Node nxt : g.get(u)) {
int v = nxt.idx; // 도착 노드
int w = nxt.cost; // 해당 노드까지의 거리
// 현재 저장된 v까지의 거리가 u를 경유한 거리보다 길다면 길이 업데이트
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.add(new Node(v, dist[v]));
}
}
}
return dist;
}- 각 노드까지의 거리를 저장 후 리턴
int[] start = dijkstra(rev, x); // i -> x
int[] end = dijkstra(map, x); // x -> i- 각 시작점별
x까지의 거리와 x에서 시작점까지의 거리를 저장합니다.
int answer = 0;
for (int i = 1; i <= n; i++) {
if (start[i] == INF || end[i] == INF) continue;
answer = Math.max(answer, start[i] + end[i]);
}
System.out.println(answer);- 왕복할 수 없다면 다음 거리를 탐색합니다.
- 왕복 가능하다면, 정답 변수와 왕복 거리 중 최대 값을 비교합니다.
- 최댓값을 출력하면 끝
코드
import java.util.*;
import java.io.*;
public class Main {
static class Node implements Comparable<Node> {
int idx, cost;
Node (int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
static int n, m, x, answer;
static List<ArrayList<Node>> map, rev;
static final int INF = 1_000_000_000;
private static int[] dijkstra(List<ArrayList<Node>> g, int start) {
int[] dist = new int[n+1];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
int u = cur.idx;
int d = cur.cost;
if (dist[u] < d) continue;
for (Node nxt : g.get(u)) {
int v = nxt.idx;
int w = nxt.cost;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.add(new Node(v, dist[v]));
}
}
}
return dist;
}
public static void main(String[] args) throws IOException {
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());
map = new ArrayList<>();
rev = new ArrayList<>();
for (int i = 0; i <= n; i++) {
map.add(new ArrayList<>());
rev.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
map.get(u).add(new Node(v, w));
rev.get(v).add(new Node(u, w));
}
int[] start = dijkstra(rev, x);
int[] end = dijkstra(map, x);
int answer = 0;
for (int i = 1; i <= n; i++) {
if (start[i] == INF || end[i] == INF) continue;
answer = Math.max(answer, start[i] + end[i]);
}
System.out.println(answer);
}
}