https://www.acmicpc.net/problem/1916
수업시간에 배운 다익스트라 코드 적용해서 풀었습니다!!
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
public class Main {
private static class Edge implements Comparable<Edge> {
int v, w;
public Edge(int v, int w) {
super();
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
}
// 오버플로우 방지를 위해 2bit 이동
private static final int INF = Integer.MAX_VALUE >> 2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
List<Edge>[] adj = new ArrayList[N+1];
for (int i = 1; i < N+1; i++) {
adj[i] = new ArrayList<>();
}
int from, to, cost;
for (int i = 0; i < M; i++) {
stk = new StringTokenizer(br.readLine());
from = Integer.parseInt(stk.nextToken());
to = Integer.parseInt(stk.nextToken());
cost = Integer.parseInt(stk.nextToken());
adj[from].add(new Edge(to, cost));
}
// 출발점의 도시번호와 도착점의 도시번호
stk = new StringTokenizer(br.readLine());
from = Integer.parseInt(stk.nextToken());
to = Integer.parseInt(stk.nextToken());
Edge[] D = new Edge[N+1];
PriorityQueue<Edge> pq = new PriorityQueue<>();
// 출발점 : from
for (int i = 1; i < N+1; i++) {
if (i == from) {
D[i] = new Edge(i, 0);
} else {
D[i] = new Edge(i, INF);
}
pq.add(D[i]);
}
boolean[] check = new boolean[N+1];
while(!pq.isEmpty()) {
Edge edge = pq.poll();
// 최단경로 갱신
for (Edge next : adj[edge.v]) {
if (!check[next.v] && D[next.v].w > D[edge.v].w + next.w) {
D[next.v].w = D[edge.v].w + next.w;
pq.remove(D[next.v]);
pq.add(D[next.v]);
}
}
check[edge.v] = true;
}
System.out.println(D[to].w);
}
}
https://www.acmicpc.net/problem/1238
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
private static class Edge implements Comparable<Edge> {
int v, w;
public Edge(int v, int w) {
super();
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
@Override
public String toString() {
return "Edge [v=" + v + ", w=" + w + "]";
}
}
private static final int INF = Integer.MAX_VALUE >> 2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
stk = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
int X = Integer.parseInt(stk.nextToken());
List<Edge>[] adj = new ArrayList[N+1];
List<Edge>[] reverseAdj = new ArrayList[N+1];
for (int i = 1; i < N+1; i++) {
adj[i] = new ArrayList<>();
reverseAdj[i] = new ArrayList<>();
}
int from, to, cost;
for (int i = 0; i < M; i++) {
stk = new StringTokenizer(br.readLine());
from = Integer.parseInt(stk.nextToken());
to = Integer.parseInt(stk.nextToken());
cost = Integer.parseInt(stk.nextToken());
// 정방향 인접리스트
adj[from].add(new Edge(to, cost));
// 모든 마을에서 파티로 가는 최단경로를 계산하기 위해 역방향 인접리스트 생성
reverseAdj[to].add(new Edge(from, cost));
}
// 파티 장소에서 모든 정점으로의 최단거리
Edge[] fromX = new Edge[N+1];
PriorityQueue<Edge> pq = new PriorityQueue<>();
for (int i = 1; i < N+1; i++) {
if (i == X) {
fromX[i] = new Edge(i, 0);
} else {
fromX[i] = new Edge(i, INF);
}
pq.add(fromX[i]);
}
boolean[] check = new boolean[N+1];
while(!pq.isEmpty()) {
Edge edge = pq.poll();
for (Edge next : adj[edge.v]) {
if (!check[next.v] && fromX[next.v].w > fromX[edge.v].w + next.w) {
fromX[next.v].w = fromX[edge.v].w + next.w;
pq.remove(fromX[next.v]);
pq.add(fromX[next.v]);
}
}
check[edge.v] = true;
}
// 모든 정점에서 파티 장소로 가는 최단거리 (방향을 뒤집은 인접리스트 사용)
pq.clear();
Edge[] toX = new Edge[N+1];
for (int i = 1; i < N+1; i++) {
if (i == X) {
toX[i] = new Edge(i, 0);
} else {
toX[i] = new Edge(i, INF);
}
pq.add(toX[i]);
}
Arrays.fill(check, false);
while(!pq.isEmpty()) {
Edge edge = pq.poll();
for (Edge next : reverseAdj[edge.v]) {
if (!check[next.v] && toX[next.v].w > toX[edge.v].w + next.w) {
toX[next.v].w = toX[edge.v].w + next.w;
pq.remove(toX[next.v]);
pq.add(toX[next.v]);
}
}
check[edge.v] = true;
}
int max = 0;
for (int i = 1; i < N+1; i++) {
max = Math.max(max, toX[i].w + fromX[i].w);
}
System.out.println(max);
}
}
https://www.acmicpc.net/problem/11404
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static final int INF = Integer.MAX_VALUE >> 2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[][] map = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(map[i], INF);
}
int to, from, cost;
for (int i = 0; i < M; i++) {
stk = new StringTokenizer(br.readLine());
from = Integer.parseInt(stk.nextToken()) - 1;
to = Integer.parseInt(stk.nextToken()) - 1;
cost = Integer.parseInt(stk.nextToken());
map[from][to] = Math.min(map[from][to], cost);
}
for (int k = 0; k < N; k++) { // 경유지
for (int i = 0; i < N; i++) { // 출발지
if (i==k) continue;
for (int j = 0; j < N; j++) { // 도착지
if (i == j || j==k) continue;
if (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == INF) sb.append(0).append(" ");
else sb.append(map[i][j]).append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
}
https://www.acmicpc.net/problem/1956
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static final int INF = Integer.MAX_VALUE >> 2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
stk = new StringTokenizer(br.readLine());
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
int[][] map = new int[V][V];
for (int i = 0; i < V; i++) {
Arrays.fill(map[i], INF);
}
int from, to, cost;
for (int i = 0; i < E; i++) {
stk = new StringTokenizer(br.readLine());
from = Integer.parseInt(stk.nextToken()) - 1;
to = Integer.parseInt(stk.nextToken()) - 1;
cost = Integer.parseInt(stk.nextToken());
map[from][to] = cost;
}
for (int k = 0; k < V; k++) { // 경유지
for (int i = 0; i < V; i++) { // 출발지
if (i == k) continue;
for (int j = 0; j < V; j++) { // 도착지
if (j == k || i == j) continue;
if(map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
int ans = INF;
for (int i = 0; i < V; i++) {
for (int j = i+1; j < V; j++) {
ans = Math.min(ans, map[i][j] + map[j][i]);
}
}
if (ans == INF) System.out.println(-1);
else System.out.println(ans);
}
}