백준/1504 특정한 최단 경로/ 다익스트라 알고리즘

특정한 최단 경로

 

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

1 초

256 MB

59864

15172

10258

24.557%

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1 복사

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 복사

7

 

---

풀이

시작점 ~ 경유지1 로 가는 최소비용  + 경유지1 ~ 경유지2 로 가는 최소비용 + 경유지2~ 목적지로 가는 최소비용의 총 합과

 

시작점 ~ 경유지2 로 가는 최소비용  + 경유지2 ~ 경유지1 로 가는 최소비용 + 경유지1~ 목적지로 가는 최소비용의 총 합을

 

비교해서 더 작은 비용의 값을 출력해준다.

 

각각 다익스트라 알고리즘을 돌면서, 이전의 다익스트라 알고리즘이 최소비용을 구하기 위해 지나갔던 간선에 대해서는 신경안쓰기 때문에,  지나갔던 간선도 자동으로 고려된다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] distance;
    static int v,e,v1,v2;
    static List<List<Node>> graph;
    static final int maxRange = 200000000; // 200000 * 1000

    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        v = input[0];
        e = input[1];
        distance = new int[v + 1];
        Arrays.fill(distance,maxRange+1);
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            int[] graphInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            graph.get(graphInfo[0]).add(new Node(graphInfo[1], graphInfo[2]));
            graph.get(graphInfo[1]).add(new Node(graphInfo[0], graphInfo[2]));
        }
        String[] v1v2 = br.readLine().split(" ");
        v1 = Integer.parseInt(v1v2[0]);
        v2 = Integer.parseInt(v1v2[1]);


    }
    static void solve() throws IOException {

        int sum1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, v);
        int sum2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, v);

        int anwser = (sum1 > maxRange && sum2 > maxRange) ? -1 : Math.min(sum1, sum2);
        bw.write(anwser+" ");

    }


    static int dijkstra(int start, int end) throws IOException {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        pq.add(new Node(start, 0));
        Arrays.fill(distance,maxRange+1);  //전역변수로 distance를 사용할것이고 다익스트라를 반복해서 사용하려면 초기화도 반복해준다.
        distance[start] = 0; //시작위치는 비용이 들지않으므로 0으로 초기화해둬야한다.

        while (!pq.isEmpty()) {
            Node pqNode = pq.poll();

            if (distance[pqNode.index] < pqNode.cost) { // 값이 같은 순간 => distance값이 갱신되서 큐에 들어갔고, 우선순위상 해당 노드가 지금 뽑혔다.
                continue;
            }

            for (Node adjNode : graph.get(pqNode.index)) {
                if (distance[adjNode.index] > distance[pqNode.index] + adjNode.cost) {
                    distance[adjNode.index] = distance[pqNode.index] + adjNode.cost;
                    pq.add(new Node(adjNode.index, distance[adjNode.index]));
                }
            }

        }
        return distance[end];
    }


    static class Node {
        int index;
        int cost;

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



}

 

 

 

 

https://steady-coding.tistory.com/82