Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?

Java / Python

2. 특정한 최단 경로

1504번

규칙을 만족하는 최단 거리를 구하는 문제

이번 문제는 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하는 문제입니다.
다익스트라 알고리즘(Dijkstra Algorithm)을 이용합니다.

• Java

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

class Node implements Comparable<Node>{
	int end, weight;

	public Node(int end, int weight){
		this.end = end;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		return weight - o.weight;
	}
}

public class Main {
	static int N, E;
	static ArrayList<ArrayList<Node>> graph; 
	static int[] dist; 
	static boolean[] check; 
	static final int INF = 200000000;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st = new StringTokenizer(br.readLine()); 
        
		N = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
        
		graph = new ArrayList<>();
		dist = new int[N+1];
		check = new boolean[N+1];
        
		Arrays.fill(dist, INF);
        
		for(int i = 0; i <= N; i++)
			graph.add(new ArrayList<>());
        
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());            
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
            
			// start에서 end로 가는 weight
			graph.get(start).add(new Node(end, weight));
 
			// end에서 start로 가는 weight 
			graph.get(end).add(new Node(start, weight));
		}

		// 반드시 거쳐야 하는 정점.
		st = new StringTokenizer(br.readLine());
		int v1 = Integer.parseInt(st.nextToken());
		int v2 = Integer.parseInt(st.nextToken());
 
		// 1 -> v1 -> v2 -> N
		int res1 = 0;
		res1 += dijkstra(1, v1);
		res1 += dijkstra(v1, v2);
		res1 += dijkstra(v2, N);
 
		// 1 -> v2 -> v1 -> N
		int res2 = 0;
		res2 += dijkstra(1, v2);
		res2 += dijkstra(v2, v1);
		res2 += dijkstra(v1, N);
        
		int result = (res1 >= INF && res2 >= INF) ? -1 : Math.min(res1, res2);
			
		bw.write(result + "\n");
    
		bw.flush();
		bw.close();
		br.close();
	}

	public static int dijkstra(int start, int end) { 
		Arrays.fill(dist, INF);
		Arrays.fill(check, false);
        
		PriorityQueue<Node> pqueue = new PriorityQueue<>();
		boolean[] check = new boolean[N + 1];
		pqueue.offer(new Node(start, 0));
		dist[start] = 0;

		while (!pqueue.isEmpty()) {
			Node now = pqueue.poll();
			int cur = now.end;
            
			if(!check[cur]){
				check[cur] = true;
                
				for (Node node : graph.get(cur)) {
					if(!check[node.end] && dist[node.end] > dist[cur] + node.weight){
						dist[node.end] = dist[cur] + node.weight;            
						pqueue.offer(new Node(node.end, dist[node.end]));
					}                             
				}                
			}
		}
		return dist[end];
	}
}

• Python

from heapq import heappush, heappop
import sys
inf = sys.maxsize
N, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]

for i in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append([b, c])
    graph[b].append([a, c])
v1, v2 = map(int, sys.stdin.readline().split())

# dijkstra 경로 탐색
def dijkstra(start):
    dp = [inf for i in range(N + 1)]
    dp[start] = 0
    heap = []
    heappush(heap, [0, start])
    while heap:
        w, c = heappop(heap)
        for n_n, n_w in graph[c]:
            weight = n_w + w
            if dp[n_n] > weight:
                dp[n_n] = weight
                heappush(heap, [weight, n_n])
    return dp

one = dijkstra(1)
v1_n = dijkstra(v1)
v2_n = dijkstra(v2)
cnt = min(one[v1] + v1_n[v2] + v2_n[N], one[v2] + v2_n[v1] + v1_n[N])
print(cnt if cnt < inf else -1)