[BOJ/백준] 30985 - 직장인 파댕이의 사회생활

30985번: 직장인 파댕이의 사회생활

---

층을 생각하지 않는다

 

1부터 X번방까지 최소 거리

X번방부터 N번방까지 최소 거리

 

다익스트라

---

---

• 제목

직장인 파댕이의 사회생활

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

파댕이는 중견기업 회사에서 직장인으로 일하고 있다. 사장님이 직장인 파댕이를 무척 아끼기 때문에, 파댕이는 사장실에 찾아가 사장님께 인사를 하려고 한다.

직장인 파댕이의 회사가 있는 건물은 K층으로 구성되어 있는데 각 층은 방과 복도로 구성되어 있다. 복도를 통해 방과 방 사이를 양방향으로 이동할 수 있다. 모든 층은 같은 모습을 하고 있다. 파댕이는 현재 1층의 1번 방에 있고, 사장실은 K층의 N번 방이다. 파댕이는 현재 자신의 위치에서부터 사장실까지 최소 시간을 사용하여 도착할 방법을 찾아야 한다.

파댕이는 각각의 복도를 지나가는 데 걸리는 시간이 얼마인지 알고 있다. 더불어 어떤 방에는 엘리베이터가 있어서 그 엘리베이터를 타고 위층으로 올라갈 수 있다. 한 층의 i번 방에 설치된 엘리베이터는 다른 층에 있는 모든 i번 방을 연결한다. 특정 엘리베이터에만 사람이 몰릴 수 있기 때문에 어떤 엘리베이터는 빠르고 어떤 엘리베이터는 느릴 수 있다. 파댕이는 각각의 엘리베이터가 한 층을 올라가는 데 걸리는 시간이 얼마인지도 알고 있다.

건물의 모습과 엘리베이터의 속도가 주어지면, 파댕이가 사장실까지 가는 최소 시간을 계산하는 프로그램을 작성하시오.

---

• 입력

첫째 줄에 방의 수 N (2 ≤ N ≤ 100,000)과 복도의 수 M (1 ≤ M ≤ 300,000), 건물의 층수 K (2 ≤ K ≤ 200,000)가 공백으로 구분되어 주어진다.

다음 줄부터 M개의 줄에 걸쳐 세 정수 u, v, c가 공백으로 구분되어 주어진다. (1 ≤ u, v ≤ N, 1 ≤ c ≤ 100,000,000, u ≤ v) 이는 u번 방과 v번 방을 잇는 복도가 존재하며 이를 지나가는 데 걸리는 시간이 c라는 뜻이다.

임의의 서로 다른 두 방에 대해 한쪽 방에서 다른 쪽 방으로 이어진 복도는 1개 이하다.

다음 줄에 N개의 정수 e1, .. , eN이 공백으로 구분되어 주어진다. (ei = -1 or 1 ≤ ei ≤ 100,000,000) 이는 i번째 방에 존재하는 엘리베이터를 타면 한 층을 올라갈 때마다 ei의 시간이 든다는 뜻이다. 만약 i번째 방에 엘리베이터가 존재하지 않는다면, ei = -1이다.

---

• 출력

파댕이가 사장실까지 가는 최소 시간을 출력한다. 만약 파댕이가 사장실에 도달할 수 없다면 -1을 출력한다.

---

예제 입력1	예제 출력1
5 7 4 1 2 7 1 3 11 1 4 7 2 3 13 2 4 4 2 5 16 4 5 10 3 -1 1 3 -1	26

 

예제 입력2	예제 출력2
3 2 7 1 2 3 2 3 8 -1 -1 -1	-1

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class NODE implements Comparable<NODE> {

        int index;
        Long cost;

        public NODE(int index, Long cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(NODE o) {
            return Long.compare(this.cost, o.cost);
        }
    }

    static void dijkstra(int STD, int start) {
        PriorityQueue<NODE> pq = new PriorityQueue<>();
        pq.add(new NODE(start, 0L));
        distance[STD][start] = 0;

        while (!pq.isEmpty()) {
            NODE curr = pq.poll();

            if (distance[STD][curr.index] < curr.cost) continue;

            for (NODE next : edge[curr.index]) {
                if (distance[STD][next.index] <= distance[STD][curr.index] + next.cost) continue;
                distance[STD][next.index] = distance[STD][curr.index] + next.cost;
                pq.add(new NODE(next.index, distance[STD][next.index]));
            }
        }
    }

    static int N, M, K;
    static long[] elevator;
    static long[][] distance;
    static ArrayList<NODE>[] edge;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        edge = new ArrayList[N + 1];
        distance = new long[2][N + 1];
        for (int i = 0; i <= N; i++) {
            edge[i] = new ArrayList<>();
            distance[0][i] = Long.MAX_VALUE;
            distance[1][i] = Long.MAX_VALUE;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            edge[u].add(new NODE(v, c));
            edge[v].add(new NODE(u, c));
        }

        dijkstra(0, 1);
        dijkstra(1, N);

        elevator = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            elevator[i] = Long.parseLong(st.nextToken());
        }

        long answer = Long.MAX_VALUE;
        for (int i = 1; i <= N; i++) {
            if (distance[0][i] == Long.MAX_VALUE) continue;
            if (distance[1][i] == Long.MAX_VALUE) continue;
            if (elevator[i] == -1) continue;
            answer = Math.min(answer, distance[0][i] + distance[1][i] + elevator[i] * (K - 1));
        }
        System.out.println(answer == Long.MAX_VALUE ? -1 : answer);
    }
}