[백준 1504] 특정한 최단경로 - JAVA //le_effort

특정한 최단 경로

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	29035	7631	4938	24.412%

문제

방향성이 없는 그래프가 주어진다. 세준이는 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)

출력

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

예제 입력 1

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

예제 출력 1

xxxxxxxxxx
7

 

 

풀이

다익스트라를 이용해서 풀이하면 됐습니다.

 

우선, 한 정점에서 모든 정점에 대한 거리를 알아야 하니 다익스트라로 풀어야겠다 라고 생각을 했습니다.

 

v1과 v2는 무조건 지나치면서 최단경로를 구해야 하는데

이는 다익스트라를 응용하면 풀 수 있습니다.

 

다익스트라를 총 3번 돌립니다.

한번의 다익스트라를 돌리면 시작정점에서 모든 정점까지의 거리를 알 수 있습니다.

 

즉 1번정점에서 부터 시작하니 1번 정점에서의 다익스트라를 돌리면

1번을 출발점으로 했을 때 모든 정점의 거리를 알 수 있습니다.

 

그리고 v1에서 다익스트라를 돌리면 v1을 출발점으로 했을때의 모든 정점의거리

v2에서 다익스트라를 돌리면 v2를 출발점으로 했을 때의 모든 정점 거리를 알 수 있습니다.

 

그래서 아래 2개의 예시중 최솟값으로 구하면 됩니다.

1번 -> v1 - > v2 - > N

1번 -> v2-> v1 -> N

 

문제의 조건에서 한번 이동했던 간선도 이동할 수 있다는 것은 구현에서 딱히 신경을 쓰실 필요는 없습니다. 이 부분은 아래의 예를 해결하기 위함입니다.

 

예를들어 1번간선에서 v1으로 가고 (1->v1) 또 여기서 v1->v2로 갈 때(1->v1->v2) v1->v2로 바로 가는 것 보다 v1->1->v2로 가는게 비용이 더 적을수 있습니다.

 

하지만 저희는 총 3번의 다익스트라를 돌렸죠

v1을 출발점으로 다익스트라를 돌리면 v1->v2로 가는것은 어차피 v1->v2로 가던 v1->1->v2로 가던

최소값이 들어가게 되니 신경쓰지 않아도 됩니다.

 

INF를 987654321로 남아서 INF가 오버플로가 발생하면 음수가되니

INF == 987654321 || INF <0이면 길이 없다고 판단했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class Main {
    static int n,e;
    static ArrayList<Node>list[];
    static boolean visited[];
    static int dist[][];
    public static void main(String[] args) throws  IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        
        n = Integer.parseInt(t[0]);
        e = Integer.parseInt(t[1]);
        
        list = new ArrayList[n+1];
        visited = new boolean[n+1];
        dist = new int[3][n+1];
        
        int INF = 987654321;
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i=0; i<3; i++) {
            Arrays.fill(dist[i], INF);
        }
        for(int i=0; i<e; i++) {
            t = br.readLine().split(" ");
            
            int a = Integer.parseInt(t[0]);
            int b = Integer.parseInt(t[1]);
            int c = Integer.parseInt(t[2]);
            
            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
        }
        
        
        t = br.readLine().split(" ");
        int v1 = Integer.parseInt(t[0]);
        int v2 = Integer.parseInt(t[1]);
        
        djistra(1,0);
        djistra(v1,1);
        djistra(v2,2);
        
        
        int total = 0;
        int total2 = 0;
        
        total = dist[0][v1]+dist[1][v2]+dist[2][n];
        total2 = dist[0][v2]+ dist[2][v1]+dist[1][n];
        
        int ans = Math.min(total, total2);
        if(ans == INF || ans<0) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
    public static void djistra(int start, int cnt) {
        visited = new boolean[n+1];
        PriorityQueue<Node>pq = new PriorityQueue<>();
        pq.add(new Node(start,0));      // 시작도시는 1번
        dist[cnt][start] = 0;
        
        while(!pq.isEmpty()) {
            Node a=  pq.poll();
            visited[a.city] = true;
            for(Node tmp : list[a.city]) {
                if(visited[tmp.city]) {
                    continue;
                }
                if(dist[cnt][tmp.city] > dist[cnt][a.city]+ tmp.w) {
                    dist[cnt][tmp.city] = dist[cnt][a.city]+tmp.w;
                    pq.add(new Node(tmp.city,dist[cnt][tmp.city]));
                }
            }
        }
    }
}
class Node implements Comparable<Node>{
    int city,w;
    Node(int city, int w){
        this.city = city;
        this.w= w;
    }
    public int compareTo(Node o) {
        return this.w - o.w;
    }
}