백준1238_파티

문제

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

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

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

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

입력

첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 

10

[코드]

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static LinkedList<CityGraph> list[];
    public static int dist[];
    public static boolean visited[];
    public static int INF = 100000000;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        int X = sc.nextInt(); //가고자 하는 목표 도시
        
        list = new LinkedList[N+1];
        dist = new int[N+1];
        visited = new boolean[N+1];
        for(int i = 1 ; i <= N; i++){
            list[i] = new LinkedList<CityGraph>();
            dist[i] = INF;
        }
        
        for(int i = 0 ; i < M; i++){
            int v = sc.nextInt();
            int d = sc.nextInt();
            int w = sc.nextInt();
            CityGraph g = new CityGraph(d, w);
            list[v].add(g);
        }
        
        int[] result = new int[N+1];
        for(int i = 1; i<=N;i++)
        {
            dist[i] = 0;
            Dijkstra(i);
            
            if(i==X){
                for(int j = 1; j<=N; j++){
                    result[j] += dist[j];    
                }    
            }else{
                result[i] += dist[X];
            }
            
            for(int j = 1; j<=N; j++){
                dist[j] = INF;    
                visited[j] = false;
            }
        }
        
        int max = 0;
        for(int j = 1; j<= N; j++)
            max = Math.max(max, result[j]);
        
        System.out.println(max);
    }
    
    public static void Dijkstra(int X){
        int Q = 0;
        while(Q != list.length-1){
            int cur = distractMin();
            visited[cur] = true;
            Q++;
            Iterator<CityGraph> it = list[cur].iterator();
            while(it.hasNext()){
                CityGraph g = it.next();
                int next_v = g.getVertex();
                int next_w = g.getWeight();
                
                if(!visited[next_v] && dist[next_v] > next_w + dist[cur]){
                    dist[next_v] = dist[cur] + next_w;
                }
            }
        }
    }
    
    public static int distractMin(){
        int min = INF;
        int piv = -1;
        for(int i = 1; i<dist.length; i++){
            if(min > dist[i] && !visited[i]){
                min = dist[i];
                piv = i;
            }
        }
        return piv;
    }
}
 
class CityGraph{
    
    int vertex;
    int weight;
 
    public CityGraph(int vertex, int weight){
        this.vertex = vertex;
        this.weight = weight;
    }
 
    public int getVertex() {
        return vertex;
    }
 
    public void setVertex(int vertex) {
        this.vertex = vertex;
    }
 
    public int getWeight() {
        return weight;
    }
 
    public void setWeight(int weight) {
        this.weight = weight;
    }
 
    
}

[알고리즘]

이 문제는 특이하게도, 왕복 거리를 구하라고 해서, 모든 정점을 시작점으로 하는 모든 최단 거리를 구해야 했다. 

그리고 해당 X 마을 까지 갔다가 오는 거리를 더해줘서 가장 큰 수를 출력해줬다.