[BOJ / JAVA] 1504 - 특정한 최단 경로

문제

풀이

주어지는 노선이 양방향이므로 다익스트라 알고리즘을 3번 이용하여 풀었습니다.

입력받는 위치는 총 4가지 입니다.

1과 N, 필수로 들러야 하는 start와 end.

다익스트라 알고리즘을 1, N, start 에서 이용하여 각 경로로 가는 최단거리를 구합니다.

여기서 1 -> start + N -> end 와 1 -> end + N ->start 를

비교하여 더 작은 값을 얻습니다. (start -> end는 동일, 양방향)

 이 값에 start -> end 의 최단거리를 더하여 답을 얻습니다.

예외 처리) start가 1과 같은 경우, end와 N이 같은 경우엔 해당 연산을 삭제합니다.

코드

import java.io.*;
import java.util.*;

class Main {
		static boolean visit[];
		static int field[][];
		static int n;
		static int m;
		static void find1(int i) {
			for(int j=1;j<=n;j++) {
				int k = find(i);
				if(k==i) break;
				for(int p=1;p<=n;p++) {
					if(p!=i)
					if(field[i][k]+field[k][p] <field[i][p])
						field[i][p] = field[i][k]+field[k][p];
				}
			}
		}
		
		static int find(int i) {
			int temp = Integer.MAX_VALUE;
			int index=i;
			for(int j=1;j<=n;j++) {
				if(field[i][j] != 99999999)
					if(i!=j)
				if(field[i][j]<temp && !visit[j]) {
					temp = field[i][j];
					index = j;
				}
			}
			visit[index] = true;
			return index;
		}
		
		static public void main(String[] args) throws IOException{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			field = new int [n+1][n+1];
			visit = new boolean[n+1];
			for(int i=1;i<=n;i++) {
				Arrays.fill(field[i], 99999999);
			}
			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());
				field[a][b] = c;
				field[b][a] = c;
			}
			
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			find1(1);
			Arrays.fill(visit, false);
			find1(n);
			Arrays.fill(visit, false);
			find1(start);
			int ans = 0;
//			for(int i=1;i<=n;i++) {
//				for(int j=1;j<=n;j++) {
//					System.out.print(field[i][j]);
//				}
//				System.out.println();
//			}
			if(start ==1 && end ==n) {
				
			}
			else {
			if(start == 1)
				ans = field[n][end];
			else if(end == n)
				ans = field[1][start];
			else {
			
			if(field[1][start] + field[n][end] > field[1][end] + field[n][start])
				ans = field[1][end] + field[n][start];
			else
				ans = field[1][start] + field[n][end];
			}
			}
			ans += field[start][end];
			
			if(ans >= 99999999)
				bw.write("-1");
			else
			bw.write(String.valueOf(ans));
			
			
			bw.flush();
		
		}
	}

결과