[BOJ 1956] 운동
접근 방법 ?
-
최단 사이클 경로를 구하면 된다,
-
다익스트라를 이용해서 최단 거리를 구할 때, 출발점에 대한 거리를 0이 아닌 최댓값으로 초기화해서, 출발점까지 도달할 수 있도록 구현
-
플로이드 워셜 알고리즘을 이용해서도 해결 가능
다익스트라 ?
-
다익스트라는 우선순위큐를 이용해서 구현
-
거리에 대한 배열을 선언해, 우선순위큐의 아이템이 구해진 거리보다 크다면 드랍시키도록 구현, 등호를 쓰지 않도록 주의
-
시간복잡도는 O(ElogE)이 발생
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(br.readLine());
List<Integer>[] list;
int[][] cost;
int answer = Integer.MAX_VALUE;
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
cost = new int[V + 1][V + 1];
list = new List[V + 1];
for(int i = 1; i <= V; i++){
list[i] = new ArrayList<>();
}
for(int i = 0; i < E; i++){
stk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stk.nextToken());
int b = Integer.parseInt(stk.nextToken());
int c = Integer.parseInt(stk.nextToken());
list[a].add(b);
cost[a][b] = c;
}
for(int i = 1; i <= V; i++){
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[1] - b[1]));
pq.add(new int[]{i, 0});
int[] dist = new int[V + 1];
for(int j = 1; j <= V; j++) dist[j] = Integer.MAX_VALUE;
int result = Integer.MAX_VALUE;
while(!pq.isEmpty()){
int[] e = pq.poll();
if(dist[e[0]] < e[1]) continue;
for(int next : list[e[0]]){
if(dist[next] > e[1] + cost[e[0]][next]){
dist[next] = e[1] + cost[e[0]][next];
pq.add(new int[]{next, dist[next]});
}
}
}
answer = Math.min(answer, dist[i]);
}
if(answer == Integer.MAX_VALUE)
bw.write("-1\n");
else
bw.write(answer + "\n");
bw.flush();
}
}
플로이드 워셜 ?
-
자기 자신에 대한 거리는 최댓값으로 초기화
-
시간복잡도는 O(V^3)
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(br.readLine());
List<Integer>[] list;
int[][] cost;
int[][] dist;
int answer = Integer.MAX_VALUE;
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
cost = new int[V + 1][V + 1];
dist = new int[V + 1][V + 1];
list = new List[V + 1];
for(int i = 1; i <= V; i++){
list[i] = new ArrayList<>();
}
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
dist[i][j] = Integer.MAX_VALUE;
}
}
for(int i = 0; i < E; i++){
stk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stk.nextToken());
int b = Integer.parseInt(stk.nextToken());
int c = Integer.parseInt(stk.nextToken());
list[a].add(b);
cost[a][b] = c;
dist[a][b] = c;
}
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
for(int k = 1; k <= V; k++){
if(dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE){
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for(int i = 1; i <= V; i++)
answer = Math.min(answer, dist[i][i]);
if(answer == Integer.MAX_VALUE)
bw.write("-1\n");
else
bw.write(answer + "\n");
bw.flush();
}
}
Author And Source
이 문제에 관하여([BOJ 1956] 운동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kwon_yongil_/BOJ-1956-운동
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
최단 사이클 경로를 구하면 된다,
다익스트라를 이용해서 최단 거리를 구할 때, 출발점에 대한 거리를 0이 아닌 최댓값으로 초기화해서, 출발점까지 도달할 수 있도록 구현
플로이드 워셜 알고리즘을 이용해서도 해결 가능
-
다익스트라는 우선순위큐를 이용해서 구현
-
거리에 대한 배열을 선언해, 우선순위큐의 아이템이 구해진 거리보다 크다면 드랍시키도록 구현, 등호를 쓰지 않도록 주의
-
시간복잡도는 O(ElogE)이 발생
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(br.readLine());
List<Integer>[] list;
int[][] cost;
int answer = Integer.MAX_VALUE;
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
cost = new int[V + 1][V + 1];
list = new List[V + 1];
for(int i = 1; i <= V; i++){
list[i] = new ArrayList<>();
}
for(int i = 0; i < E; i++){
stk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stk.nextToken());
int b = Integer.parseInt(stk.nextToken());
int c = Integer.parseInt(stk.nextToken());
list[a].add(b);
cost[a][b] = c;
}
for(int i = 1; i <= V; i++){
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[1] - b[1]));
pq.add(new int[]{i, 0});
int[] dist = new int[V + 1];
for(int j = 1; j <= V; j++) dist[j] = Integer.MAX_VALUE;
int result = Integer.MAX_VALUE;
while(!pq.isEmpty()){
int[] e = pq.poll();
if(dist[e[0]] < e[1]) continue;
for(int next : list[e[0]]){
if(dist[next] > e[1] + cost[e[0]][next]){
dist[next] = e[1] + cost[e[0]][next];
pq.add(new int[]{next, dist[next]});
}
}
}
answer = Math.min(answer, dist[i]);
}
if(answer == Integer.MAX_VALUE)
bw.write("-1\n");
else
bw.write(answer + "\n");
bw.flush();
}
}
플로이드 워셜 ?
-
자기 자신에 대한 거리는 최댓값으로 초기화
-
시간복잡도는 O(V^3)
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(br.readLine());
List<Integer>[] list;
int[][] cost;
int[][] dist;
int answer = Integer.MAX_VALUE;
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
cost = new int[V + 1][V + 1];
dist = new int[V + 1][V + 1];
list = new List[V + 1];
for(int i = 1; i <= V; i++){
list[i] = new ArrayList<>();
}
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
dist[i][j] = Integer.MAX_VALUE;
}
}
for(int i = 0; i < E; i++){
stk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stk.nextToken());
int b = Integer.parseInt(stk.nextToken());
int c = Integer.parseInt(stk.nextToken());
list[a].add(b);
cost[a][b] = c;
dist[a][b] = c;
}
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
for(int k = 1; k <= V; k++){
if(dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE){
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for(int i = 1; i <= V; i++)
answer = Math.min(answer, dist[i][i]);
if(answer == Integer.MAX_VALUE)
bw.write("-1\n");
else
bw.write(answer + "\n");
bw.flush();
}
}
Author And Source
이 문제에 관하여([BOJ 1956] 운동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kwon_yongil_/BOJ-1956-운동
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
자기 자신에 대한 거리는 최댓값으로 초기화
시간복잡도는 O(V^3)
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(br.readLine());
List<Integer>[] list;
int[][] cost;
int[][] dist;
int answer = Integer.MAX_VALUE;
int V = Integer.parseInt(stk.nextToken());
int E = Integer.parseInt(stk.nextToken());
cost = new int[V + 1][V + 1];
dist = new int[V + 1][V + 1];
list = new List[V + 1];
for(int i = 1; i <= V; i++){
list[i] = new ArrayList<>();
}
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
dist[i][j] = Integer.MAX_VALUE;
}
}
for(int i = 0; i < E; i++){
stk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stk.nextToken());
int b = Integer.parseInt(stk.nextToken());
int c = Integer.parseInt(stk.nextToken());
list[a].add(b);
cost[a][b] = c;
dist[a][b] = c;
}
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
for(int k = 1; k <= V; k++){
if(dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE){
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for(int i = 1; i <= V; i++)
answer = Math.min(answer, dist[i][i]);
if(answer == Integer.MAX_VALUE)
bw.write("-1\n");
else
bw.write(answer + "\n");
bw.flush();
}
}
Author And Source
이 문제에 관하여([BOJ 1956] 운동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwon_yongil_/BOJ-1956-운동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)