백준 세부 13905

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

13905번: 세부

 

다익스트라를 변형해서 풀면된다.

기존의 다익스트라가 한 정점에서 다른 정점으로의 최단거리를 구한다고 하면

변형된 다익스트라는 한 정점에서 다른 정점으로의 경로중로 이동하는 가중치의 최소값들의 최대값을 구하는 것이다.

 

예시로 든 그림을 보면 1에서 5로 가는 경로는 총 4가지다.

1) 1-2-3-5

2) 1-7-3-5

3) 1 -7-5

4) 1-7-6-5

각 경로의 가중치의 최소값을 구하면

1) 은 2

2) 는 2

3) 은 1

4) 는 3이다.

이 중에서 3이 제일 크므로 답은 3이다.

 

위에서 계산한 공식들 공식화 시키면

시작점에서 각 정점으로 가져갈수있는 최대 빼빼로 무게를 D[i]라고 정의하고,

정점 i에서 정점 j로가는 간선 edge[i][j] 있다고 하면 

D[j] = Math.max(D[j], Math.min(D[i], edge[i][j].weight) 이다.

 

최대 정점갯수가 10만 최대 간선개수가 30만이므로 평균 간선의 갯수가 3개정도이므로 인접행렬이 아닌 인접리스트를 이용하고 우선순위큐를 이용해서 각 정점을 순회하면 이 문제를 O(10만 * log(30만))시간 내에 해결할수 있다.

package 백준;
import java.util.*;
import java.io.*;

public class 세부 {
	static class MyScanner {

		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));

		}

		String next() {
			if (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}

			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

	}
	static int N,M,S,E;
	static ArrayList <int[]> edges[];
	static int INF=987654321;
	static int answer = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		N = sc.nextInt();
		M = sc.nextInt();
		S = sc.nextInt();
		E = sc.nextInt();
		edges = new ArrayList[N+1];
		
		for(int i = 0;i<=N;i++) {
			edges[i] = new ArrayList<int[]>();
		}
		
		for(int i =0 ;i <M;i++) {
			int  x = sc.nextInt();
			int  y = sc.nextInt();
			int  z = sc.nextInt();
			edges[x].add(new int[] {y,z});
			edges[y].add(new int[] {x,z});
		}
		
		PriorityQueue <int[]> pq = new PriorityQueue <int[]>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return -(o1[1]-o2[1]);
			}
			
		});
		boolean v[] = new boolean[N+1];
		int D[] = new int[N+1];
		D[S] = INF;
		pq.add(new int[]{S,0});	
		
		while(!pq.isEmpty()) {
			int now[] = pq.poll();
			if(v[now[0]]) continue;
			v[now[0]] = true;
			for(int i =0 ;i < edges[now[0]].size();i++) {
				int u = edges[now[0]].get(i)[0];
				int w = edges[now[0]].get(i)[1];
				D[u]= Math.max(D[u], Math.min(D[now[0]], w));
				pq.add(edges[now[0]].get(i));
			}
 		}
		
		answer = D[E];
		System.out.println(answer);
	}

}