[ boj : 17396 ] 백도어

www.acmicpc.net/problem/17396

17396번: 백도어

문제 : 방문할 수 없는 정점들과 방문할 수 있는 정점들이 주어지고 0번 정점부터 n-1번 정점까지 최단거리를 구하시오

 

해설 : 평범한 다익스트라 문제입니다. 다만 방문 할 수 없는 정점을 뽑았을때는 그냥 무시해주면 되겠죠. 요새 자바 공부를 하고 있어서 자바로 한번 풀어봤는데 문법적인 요소가 꽤 까다로워서 싫네요;;;

 

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

public class Main{
static int n,m;
    static int []state = new int[100000];
    static long []dist = new long[100000];
    static ArrayList<info> []adj =new ArrayList[100000];
    public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        for(int i=0;i<n;i++)
            adj[i] = new ArrayList<info>();
        input = br.readLine();
        st = new StringTokenizer(input);
        int x,y;
        long w;
        for(int i=0;i<n;i++){
            x=Integer.parseInt(st.nextToken());
            state[i]=x;
        }
        for(int i=0;i<m;i++){
            input = br.readLine();
            st = new StringTokenizer(input);
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            w = Long.parseLong(st.nextToken());
            adj[x].add(new info(y,w));
            adj[y].add(new info(x,w));
        }
        System.out.println(djik(0));
    }
    public static long djik(int x){
        for(int i=0;i<n;i++) dist[i]=(long)1e11;
        
        PriorityQueue<info> pq = new PriorityQueue<>();
        pq.add(new info(x,0));
        dist[x]=0;
        
        while(!pq.isEmpty()){
            info cur = pq.poll();
            if(cur.to==n-1)return dist[cur.to];
            if(dist[cur.to]<cur.weight || state[cur.to]==1)continue;
            for(int i=0;i<adj[cur.to].size();i++){
                int next = adj[cur.to].get(i).to;
                long next_weight = adj[cur.to].get(i).weight;
                if(dist[next]>dist[cur.to]+next_weight){
                    dist[next]=dist[cur.to]+next_weight;
                    pq.add(new info(next,dist[next]));
                }
            }
        }
        return -1;
    }
}
class info implements Comparable<info>{
    int to;
    long weight;
    info(int to,long weight){
        this.to=to;
        this.weight=weight;
    }
    @Override
    public int compareTo(info cur){
        if(this.weight<cur.weight)return -1;
        else if(this.weight==cur.weight)return 0;
        else return 1;
    }
}