1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
0. 1번 노드에서 v1,v2를 거쳐 N번 노드로 이동하는 방법은 2가지이다
- v1을 먼저 방문 : 1-v1-v2-N
- v2를 먼저 방문 : 1-v2-v1-N
- 조건상 두 지점간 거리의 최댓값은 800개의 노드 가 1000 길이의 길로 연결됬을 경우인 799K이다
1. 1번노드, v1번 노드, v2번 노드에서 각각 다익스트라를 돌려, 다른 노드로 가는 최솟값을 찾는다
2. 다익스트라 계산 후 1-v1-v2-N 과 1-v2-v1-N 두 방법 중 cost가 작은것을 찾는다
3. 이론상 최대치가 약 80만이므로, 1-v1 / v1-v2 / v2-N 3번의 이동이 다 최대 cost에 가깝다고 해도 총 cost는 240만보다 작다
- cost가 300만 이상의 결과가 나왔다면 경로가 존재하지 않아 초깃값이 계산된 경우이므로 -1을 출력한다
- 그 외라면 구한 cost를 출력한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
int[][]graph = new int[n+1][n+1];
for (int i = 0; i < m; i++) {
st=new StringTokenizer(br.readLine()," ");
int n1 = pint(st.nextToken());
int n2 = pint(st.nextToken());
int c = pint(st.nextToken());
graph[n1][n2]=c;
graph[n2][n1]=c;
}
st=new StringTokenizer(br.readLine()," ");
int n1 = pint(st.nextToken());
int n2 = pint(st.nextToken());
//다익스트라 준비물 * 3
int[]dilk1=new int[n+1];
int[]dilkn1=new int[n+1];
int[]dilkn2=new int[n+1];
Arrays.fill(dilk1, 3000000);
Arrays.fill(dilkn1, 3000000);
Arrays.fill(dilkn2, 3000000);
boolean[] isV=new boolean[n+1];
boolean[] isVn1=new boolean[n+1];
boolean[] isVn2=new boolean[n+1];
dilk1[1]=0;
dilkn1[n1]=0;
dilkn2[n2]=0;
for (int i = 0; i < n; i++) {
//아직 방문 안한 노드 중 가장 가까운 노드 탐색
int min=Integer.MAX_VALUE, minnode=0;
int minn1=Integer.MAX_VALUE, minnoden1=0;
int minn2=Integer.MAX_VALUE, minnoden2=0;
for (int j = 1; j <= n; j++) {
if(!isV[j] && dilk1[j]<min) {
min=dilk1[j];
minnode=j;
}if(!isVn1[j] && dilkn1[j]<minn1) {
minn1=dilkn1[j];
minnoden1=j;
}if(!isVn2[j] && dilkn2[j]<minn2) {
minn2=dilkn2[j];
minnoden2=j;
}
}
//해당 노드 방문처리
isV[minnode]=true;
isVn1[minnoden1]=true;
isVn2[minnoden2]=true;
for (int j = 1; j <= n; j++) {
//아직 방문 안한 노드에 대해 cost 업데이트
if(!isV[j] && graph[minnode][j]!=0) {
dilk1[j]=Math.min(dilk1[j], dilk1[minnode]+graph[minnode][j]);
}
if(!isVn1[j] && graph[minnoden1][j]!=0) {
dilkn1[j]=Math.min(dilkn1[j], dilkn1[minnoden1]+graph[minnoden1][j]);
}
if(!isVn2[j] && graph[minnoden2][j]!=0) {
dilkn2[j]=Math.min(dilkn2[j], dilkn2[minnoden2]+graph[minnoden2][j]);
}
}
}
//1->n1->n2->n
int cost=3000000;
cost = Math.min(dilk1[n1]+dilkn1[n2]+dilkn2[n], dilk1[n2]+dilkn2[n1]+dilkn1[n]);
if(cost>=3000000)System.out.println(-1);
else System.out.println(cost);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글
| [백준] 15686 - 치킨 배달 (0) | 2021.04.15 |
|---|---|
| [백준] 9935 - 문자열 폭발 (0) | 2021.04.14 |
| [백준] 1019 - 책 페이지 (0) | 2021.04.13 |
| [백준] 1566 - P배열 (0) | 2021.04.13 |
| [백준] 12865 - 평범한 배낭 (0) | 2021.04.12 |
| [백준] 17136 - 색종이 붙이기 (0) | 2021.04.12 |
| [백준] 2629 - 양팔저울 (0) | 2021.04.12 |
