백준 1238 (파티) / 다익스트라

문제

---

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

 

 

 

풀이

---

풀이 순서

1. 모든 학생에 대해서 다익스트라 알고리즘을 통해 최단거리를 구한다.

for(int i = 1 ; i <= n ; i++) {
   	Dijkstra(i);
}

 

2. X번 마을로 가는 거리와 X번마을에서 집으로 돌아가는 거리 더한값의 최대값을 구한다.

for(int i = 1; i <= n ; i++) {
    if( max < dist[x][i] + dist[i][x]) {
    	max = dist[x][i] + dist[i][x];
    }
}

 

 

<전체코드>

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

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int[][] dist;
	static List<Edge>[] list;
	static int n, m, x;
	
	static class Edge implements Comparable<Edge>{
		int v, c;
		
		public Edge(int v,int c) {
			this.v = v;
			this.c = c;
		}

		@Override
		public int compareTo(Edge e1) {
			// TODO Auto-generated method stub
			return Integer.compare(this.c, e1.c);
		}	
	}
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    String[] nmx = bufferedReader.readLine().split("\\s");
	    n = Integer.parseInt(nmx[0]);
	    m = Integer.parseInt(nmx[1]);
	    x = Integer.parseInt(nmx[2]);
	    
	    list = new ArrayList[n+1];
	    for(int i = 0 ; i <= n ; i++) {
	    	list[i] = new ArrayList<Edge>();
	    }
	    
	    for(int i = 0 ; i < m ; i++) {
	    	String[] abc = bufferedReader.readLine().split("\\s");
	    	int a = Integer.parseInt(abc[0]);
	    	int b = Integer.parseInt(abc[1]);
	    	int c = Integer.parseInt(abc[2]);
	    	
	    	list[a].add(new Edge(b, c));	    	
	    }
	    
	    dist = new int[n+1][n+1];
	    for(int i = 1 ; i <= n ; i++) {
	    	Dijkstra(i);
	    }
	    
	    int max = Integer.MIN_VALUE;
	    for(int i = 1; i <= n ; i++) {
		    if( max < dist[x][i] + dist[i][x]) {
		    	max = dist[x][i] + dist[i][x];
		    }
	    }
	        
	    System.out.println(max);
	}
	
	static void Dijkstra(int s) {
		
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		for(int i = 1 ; i <= n ; i++) {
			if(i != s) {
				dist[s][i] = Integer.MAX_VALUE;
			}
			else {
				dist[s][i] = 0;
			}
			pq.add(new Edge(i, dist[s][i]));
		}
		
		while(!pq.isEmpty()) {
			
			Edge now = pq.poll();
			
			for(Edge next : list[now.v]) {
				if(dist[s][now.v] != Integer.MAX_VALUE 
						&& (dist[s][next.v] > dist[s][now.v] + next.c)) {
					
					dist[s][next.v]= dist[s][now.v] + next.c;
					
					pq.add(new Edge(next.v, dist[s][next.v]));
				}
			}
		}
	}

}