[백준] 1238번 파티 (gold 3

import java.io.*;
import java.util.*;

class Road{
    int x;
    int t;
    public Road(int x, int t){
        this.x=x;
        this.t=t;
    }
}
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());
        int x=Integer.valueOf(st.nextToken());

        ArrayList<Road>[] arr=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            arr[i]=new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st=new StringTokenizer(br.readLine());
            int s=Integer.valueOf(st.nextToken());
            int e=Integer.valueOf(st.nextToken());
            int t=Integer.valueOf(st.nextToken());
            arr[s].add(new Road(e,t));
        }

        //출발 -> x
        int[] sx=new int[n+1];

        PriorityQueue<Road> que=new PriorityQueue<>(new Comparator<Road>(){
           public int compare(Road o1 , Road o2){
               return o1.t-o2.t;
           } 
        });
        //각 점에서 x까지의 최단 bfs로 구함. 한점에서 한점이라 굳이 다익스트라?
        //조건이 모든점 도달 가능이므로 그대로 진행.
        for(int i=1; i<=n; i++){
            if(i==x){
                continue;
            }
            int[] visit=new int[n+1];
            Arrays.fill(visit, Integer.MAX_VALUE);
            int min=Integer.MAX_VALUE;
            que.offer(new Road(i,0));
            while(!que.isEmpty()){
                Road temp=que.poll();
                if(temp.t>=min){
                    continue;
                }
                if(temp.x==x && temp.t<min){
                    min=temp.t;
                }
                for(int j=0; j<arr[temp.x].size(); j++) {
                    Road go = arr[temp.x].get(j);
                    if (visit[go.x] > temp.t + go.t) {
                        que.offer(new Road(go.x, temp.t + go.t));
                        visit[go.x]=temp.t+go.t;
                    }
                }
            }
            sx[i]=min;
        }
        //x에서 각 점들의 최단. 다익스트라 알고리즘
        //x->도착
        int[] xe=new int[n+1];
        Arrays.fill(xe,Integer.MAX_VALUE);
        que.offer(new Road(x,0));
        xe[x]=0;

        while(!que.isEmpty()){
            Road temp=que.poll();
            for(int i=0; i<arr[temp.x].size(); i++){
                Road r=arr[temp.x].get(i);
                if(r.t+temp.t>=xe[r.x]){
                    continue;
                }
                xe[r.x]=temp.t+r.t;
                que.offer(new Road(r.x , temp.t+r.t));
            }
        }

        int max=Integer.MIN_VALUE;
        for(int i=1; i<=n; i++){
            int temp=sx[i]+xe[i];
            max= max < temp ? temp:max;
        }
        bw.write(max+"");
        bw.flush();


    }
}


//다익스트라는 무조건 우선순위큐로 구현하기. 
//이렇게 할 경우가 1/2정도로 메모리가 작아짐