[Java][1238] 파티

문제:

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

1238번: 파티

코드:

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

public class Main {
    public static int v,e,st,end;
    public static ArrayList<ArrayList<Pair>> arr = new ArrayList<>(1005);
    public static int INF = Integer.MAX_VALUE;
    public static int [] d = new int[1005];
    public static int [] pre = new int[1005];
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stk = new StringTokenizer(br.readLine());
        v = Integer.parseInt(stk.nextToken());
        e = Integer.parseInt(stk.nextToken());
        end = Integer.parseInt(stk.nextToken());

        for(int i=1;i<v+5;i++){
            arr.add(new ArrayList<>());
        }
        for(int i=1;i<v+5;i++){
            d[i] = INF;
        }

        while(e-->0){
            StringTokenizer tmp = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(tmp.nextToken());
            int v = Integer.parseInt(tmp.nextToken());
            int w = Integer.parseInt(tmp.nextToken()); // 가중치

            arr.get(u).add(new Pair(w,v));
        }

        int [] result = new int[1005];

        for(int i=1;i<=v;i++){
            PriorityQueue<Pair> pq = new PriorityQueue<>();
            d[i] = 0; // 시작점
            pq.add(new Pair(d[i],i));
            while(!pq.isEmpty()){
                Pair cur = pq.poll();
                if(d[cur.num] != cur.dis) continue;
                for(Pair nxt : arr.get(cur.num)){
                    if(d[nxt.num] <= d[cur.num] + nxt.dis) continue;
                    d[nxt.num] = d[cur.num] + nxt.dis;
                    pq.add(new Pair(d[nxt.num] , nxt.num));
                }
            }

            result[i] += d[end];

            for(int j=1;j<v+5;j++){
                d[j] = INF;
            }

            pq = new PriorityQueue<>();
            d[end] = 0; // 시작점
            pq.add(new Pair(d[end],end));
            while(!pq.isEmpty()){
                Pair cur = pq.poll();
                if(d[cur.num] != cur.dis) continue;
                for(Pair nxt : arr.get(cur.num)){
                    if(d[nxt.num] <= d[cur.num] + nxt.dis) continue;
                    d[nxt.num] = d[cur.num] + nxt.dis;
                    pq.add(new Pair(d[nxt.num] , nxt.num));
                }
            }

            result[i] += d[i];

            for(int j=1;j<v+5;j++){
                d[j] = INF;
            }
        }

        int maxTime = -1;
        for(int i=1;i<=v;i++){
            maxTime = Math.max(result[i], maxTime);
        }

        System.out.println(maxTime);


    }
}

class Pair implements Comparable<Pair>{
    int dis;
    int num;

    Pair(int dis, int num){
        this.dis = dis; // 거리
        this.num = num; // 정점번호
    }

    @Override
    public int compareTo(Pair o) {
        return this.dis - o.dis;
    }
}

 

다익스트라 두번 돌리면 해결