백준 : 1939

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

1939번: 중량제한

다잌스트라를 이용해서 접근 다만 가중치에 대해서 현재까지의 합을 저장하는것이아니라 현재 수량과 다리의 값중 min의 값을 선택해서 다음 섬으로 이동시킨다.

이때 너무많은 값을 q에 push할수 있어서 시간초과하 할수 있다.

따라서 도착지점의 값보다 현재 q에 들어있는 값이 작다면 희망없는 노드이기 때문에 버린다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B1939 {
    static int N,M;
    static class Pair implements Comparable<Pair>{
        int u;
        int c;
        public Pair(int u, int c) {
            super();
            this.u = u;
            this.c = c;
        }
        @Override
        public int compareTo(Pair o) {
            if(c<o.c) {
                return 1;
            }
            return -1;
        }
        
    }
    static ArrayList<Pair> list[];
    
    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());
        M = Integer.parseInt(st.nextToken());
        
        list = new ArrayList[N+1];
        
        for(int n=1;n<=N;n++) {
            list[n] = new ArrayList<Pair>();
        }
        
        for(int m=0;m<M;m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            list[u].add(new Pair(v,c));
            list[v].add(new Pair(u,c));
        }
        
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        
        int digit[] = new int[N+1];
        PriorityQueue<Pair> q = new PriorityQueue<>();
        
        q.add(new Pair(start,Integer.MAX_VALUE));
        while(!q.isEmpty()) {
            Pair tmp = q.poll();
            if(tmp.c < digit[end])continue;
            int size = list[tmp.u].size();
            
            for(int s=0;s<size;s++) {
                int next = list[tmp.u].get(s).u;
                int c = Math.min(list[tmp.u].get(s).c,tmp.c);
                if(digit[next] < c) {
                    digit[next] = c;
                    q.add(new Pair(next,c));
                }
            }
        }
        
        System.out.println(digit[end]);
    }
}