관리 메뉴

공부공간

BOJ - 1504 ) 특정한 최단 경로 본문

그래프 알고리즘/Dijkstra

BOJ - 1504 ) 특정한 최단 경로

SangwonSeo 개발자가될수있을까? 2020. 8. 24. 22:59
728x90

 


https://www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존�

www.acmicpc.net


특정한 노드 V1,V2를 꼭 지나야하기때문에

 

1->V1->V2->N의 경우의 수와 1->V2->V1->N의 경우의 수를 모두 구해서 비교한다음 정답을 구해야한다.

 

다익스트라 알고리즘만 알고있다면, 쉽게 풀리는 문제입니다.

 

 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 특정한최단경로 {
	
	
	
	private static int n,e;
	private static int v1,v2;
	private static ArrayList<int[]> map[];
	private static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			// 간선이 짧은? 것들만 앞에 정렬
			return o1[0] - o2[0];
		}
	});
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		map = new ArrayList[n+1];
		for(int i = 1 ; i <= n ; i++) {map[i]= new ArrayList<>();}
		for(int i = 0 ; i < e ; i ++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[a].add(new int[] {b,c});
			map[b].add(new int[] {a,c});
		}
		st = new StringTokenizer(br.readLine());
		
		v1 = Integer.parseInt(st.nextToken());
		v2 = Integer.parseInt(st.nextToken());
		long answer = Math.min(Dijkstra(1,v1) + Dijkstra(v1,v2) + Dijkstra(v2,n) , Dijkstra(1,v2) + Dijkstra(v2,v1) + Dijkstra(v1,n));
		System.out.println(answer = answer >20000000 ? -1 : answer);
		
	}
	private static long Dijkstra(int s ,int e) {
		// s에서부터 e까지의 short path값을 리턴
		pq.clear();
		long path[] = new long[n+1];
		for(int i = 1 ; i <=n ; i++) path[i] = 2000000000;
		// 자기자신은 0
		path[s] =0;
		pq.add(new int[] {s,0});
		while(!pq.isEmpty()) {
			int[] now = pq.poll();
			for (int[] node : map[now[0]]) {
				if(path[node[0]] > node[1]+path[now[0]]) {
					path[node[0]] = node[1]+path[now[0]];
					pq.add(node);
				}
			}
			
		}
		
		return path[e];
	}
}

728x90

'그래프 알고리즘 > Dijkstra' 카테고리의 다른 글

BOJ - 10282 ) 해킹  (0) 2020.10.30
BOJ - 1167 ) 트리의 지름  (0) 2020.10.25
BOJ - 1504 ) 특정한 최단 경로  (0) 2020.08.24
BOJ - 1261 ) 알고스팟  (0) 2020.04.16
BOJ - 1916 ) 최소비용 구하기  (0) 2020.04.16
BOJ - 1753 ) 최단경로  (0) 2020.04.07
0 Comments
댓글쓰기 폼