백준 1238 <파티>

문제를 보면 어디 지점에서 어디까지의 최소거리 -->즉 다익스트라 알고리즘 문제이다.

 

각자의 위치에서 파티장소까지 가는 최소거리에 파티장에서 자신까지 오는 최단거리를 더하면 된다.

 

각자 위 위치에서 파티 장소까지 가는 거리는 즉 N-1*M 파티 장소에서 모든 장소까지 1*M 이므로 N*M으로 천만으로 충분하다.

 

문제 풀이

1. 각자의 위치에서 파티 장소까지 최단거리를 각각 구해서 저장한다.
2. 피티장소에서 모든 장소를 최단거리로 검색하며 각자의 위치 값에 더한다.
3. 최소 출력!

문제를 많이 풀어보는것이 알고리즘의 실력이 느는 단계라고 할 수 있다.

 

 

그림처럼 주황색 학생으로 부터 파티까지 가는 최단거리 다익스트라를 구한다.

이처럼 모든 학생의 위치에서 파티까지의 최단거리를 다익스트라로 구한다.

 

그 후 파티 장소에서 다익스트라를 적용해 각자의 최단거리를 기존의 파티 장소까지 가는 거리에 더해준다.

 

전체 코드

package solution;

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

public class Main {

	public static class point implements Comparable<point> {
		int ne;
		int d;

		public point(int ne, int d) {
			super();
			this.ne = ne;
			this.d = d;
		}

		@Override
		public int compareTo(point o) {
			// TODO Auto-generated method stub
			return this.d - o.d;
		}

	}

	static int n, m, x, dis[];
	static PriorityQueue<point> pq;
	static ArrayList<point> num[];
	static boolean visit[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		dis = new int[n + 1];
		num = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
			num[i] = new ArrayList<point>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			num[Integer.parseInt(st.nextToken())]
					.add(new point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		for (int i = 1; i <= n; i++) {
			if (i == x) {
				continue;
			}
			visit = new boolean[n + 1];
			pq = new PriorityQueue<point>();
			visit[i] = true;
			for (int j = 0; j < num[i].size(); j++) {
				pq.add(num[i].get(j));
			}
			bfs(i);
		}
		visit = new boolean[n + 1];
		visit[x] = true;
		pq = new PriorityQueue<point>();
		for (int j = 0; j < num[x].size(); j++) {
			pq.add(num[x].get(j));
		}
		finish();
		int max=0;
		for(int i=1;i<=n;i++) {
			max=Math.max(max,dis[i]);
		}
		System.out.println(max);
	}

	private static void finish() {
		// TODO Auto-generated method stub
		while (!pq.isEmpty()) {
			point next = pq.remove();
			if (visit[next.ne]) {
				continue;
			}
			dis[next.ne] += next.d;
			visit[next.ne] = true;
			for (int j = 0; j < num[next.ne].size(); j++) {
				int next1 = num[next.ne].get(j).ne;
				if (visit[next1]) {
					continue;
				}
				pq.add(new point(next1, next.d + num[next.ne].get(j).d));
			}
		}
	}

	private static void bfs(int i) {
		// TODO Auto-generated method stub
		while (!pq.isEmpty()) {
			point next = pq.remove();
			if (visit[next.ne]) {
				continue;
			}
			if (next.ne == x) {
				dis[i] = next.d;
				return;
			}
			visit[next.ne] = true;
			for (int j = 0; j < num[next.ne].size(); j++) {
				int next1 = num[next.ne].get(j).ne;
				if (visit[next1]) {
					continue;
				}
				pq.add(new point(next1, next.d + num[next.ne].get(j).d));
			}
		}
	}

}