백준 14284번 간선 이어가기2(자바) - 다익스트라

간선 이어가기 2 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

1326

761

642

57.475%

문제

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

입력

첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤5000,1≤m≤100,000)

다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다. (1≤a,b≤n,1≤c≤100,a≠b)

다음 줄에는 두 정점 s,t가 주어진다. (1≤s,t≤n,s≠t)

모든 간선을 연결하면 그래프는 연결 그래프가 됨이 보장된다.

출력

s와 t가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오,

예제 입력 1 복사

8 9
1 2 3
1 3 2
1 4 4
2 5 2
3 6 1
4 7 3
5 8 6
6 8 2
7 8 7
1 8

예제 출력 1 복사

5

---

처음에는 특정 지점에서 s, 특정 지점에서 t까지의 거리가 가장 짧은 간선들의 가중치를 구하려고 했는데

생각해보니 그냥 s와 t까지의 최단 거리를 다익스트라 알고리즘으로 구현하면 됐다.

import javax.management.InstanceNotFoundException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Node implements Comparable<Node> {
        int idx;
        int cost;
        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node node) {
            if (this.cost < node.cost)
                return -1;
            return 1;
        }
    }
    static int n,m;
    static ArrayList<Node>[] list;
    static int[] di;
    public static void main(String[] args) throws Exception{
        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];
        di = new int[n+1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
        }
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        Arrays.fill(di, 1000);
        System.out.print(dijkstra(s, t));
    }

    static int dijkstra(int start, int end) {
        di[start] = 0;
        PriorityQueue<Node> que = new PriorityQueue<>();
        que.offer(new Node(start, 0));
        while (!que.isEmpty()) {
            Node now = que.poll();
            if (di[now.idx] < now.cost) continue;
            for (int i = 0; i < list[now.idx].size(); i++) {
                int idx = list[now.idx].get(i).idx;
                int cost = list[now.idx].get(i).cost;
                if (di[now.idx] + cost < di[idx]) {
                    di[idx] = di[now.idx] + cost;
                    que.offer(new Node(idx, di[idx]));
                }
            }
        }
        return di[end];
    }
}