문제

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

소스코드

main

    static int N,R,M,K;
    static String [] city;
    static int [] arrCity;
    static int [][][] data;
    static final int INF = 999_999_999;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        city = new String [N];
        String name;
        Map<String,Integer> map =  new HashMap<>();
        st= new StringTokenizer(br.readLine()," ");
        //맵을 이용 해당 String 받을 때 value에 인덱스 값 받기
        for (int i = 0; i < N; i++) {
            name = st.nextToken();
            map.put(name,i);
        }
        //도시
        st = new StringTokenizer(br.readLine()," ");
        M = Integer.parseInt(st.nextToken());

        arrCity = new int[M];
        st = new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < M; i++) {
            name =st.nextToken();
            arrCity[i] = map.get(name);
        }
        data = new int [N][N][2];
        st = new StringTokenizer(br.readLine()," ");
        K = Integer.parseInt(st.nextToken());

        //초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                data[i][j][0]= INF;
                data[i][j][1]= INF;
            }
        }
        String type;
        int val, start,end,val2;

        // 데이터 넣어 주기
        for (int i = 0; i < K; i++) {
            st= new StringTokenizer(br.readLine());
            type = st.nextToken();
            start = map.get(st.nextToken());
            end = map.get(st.nextToken());
            val = Integer.parseInt(st.nextToken());
            val2 = discount(val*2,type);

         // 내일로 이용 금액과 다른 거 탔을때 금액
            if(data[start][end][0] > val * 2){
                data[start][end][0]= val * 2;
                data[end][start][0]= val * 2;
            }

            if(data[start][end][1] > val * 2){
                data[start][end][1] = val2;
                data[end][start][1]= val2;
            }
    }
        for (int j = 0; j <N ; j++) {
            for (int k = 0; k <N ; k++) {
                if(k == j){
                    continue;
                }

                for (int l = 0; l <N ; l++) {
                    if(k==l || l == j) continue;
                    if(data[k][l][0] > data[k][j][0]+data[j][l][0]){
                        data[k][l][0] = data[k][j][0]+data[j][l][0];
                    }
                    if(data[k][l][1] > data[k][j][1]+data[j][l][1]){
                        data[k][l][1] = data[k][j][1]+data[j][l][1];
                    }
                }
            }
        }
        if(judge()){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }

금액 계산

private static int discount(int val,String vehecle) {
        if(vehecle.equals("ITX-Saemaeul") || vehecle.equals("Mugunghwa") || vehecle.equals("ITX-Cheongchun")) return 0;
        else if(vehecle.equals("S-Train")|| vehecle.equals("V-Train") ) return val/2;
        return val;
    }

어떤걸 사야할 지 판단

 private static boolean judge(){
        int case1= 0;
        int case2= R*2;

        for (int i = 1; i < M ; i++) {
            case1 += data[arrCity[i-1]][arrCity[i]][0];
            case2 += data[arrCity[i-1]][arrCity[i]][1];
        }
        // 내일로 안사
        if(case1 <= case2){
            return false;
        }
        // 사 
        return true;
    }

생각할 것

1. 그 해당 역 이름 map으로 key값 넣고, index를 value로 가지기.
2. 플로이드 와샬 업데이트 타이밍, 초기화 하는거 생각

참고

https://952hi.tistory.com/28