[白俊]9370号未確認目的地/Java,Python


Baekjoon Online Judge


algorithm practice


-問題を逐次解く


25.最短経路


図形の幹線に重みがない場合は、BFSを使用して最短距離を検索できます.重みがあればどうなりますか?
Java/Python

3.目的地が確認されていない


9370号
最短距離アルゴリズム応用問題

始点→目的地までの最短距離で特定の幹線を通過する場合の簡単なまとめです.
「Dijkstraアルゴリズム」(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 final int INF = 10_000_000;
    	static int V, E, T;
    	static int start, g, h;
    	static int[][] graph;
    	static int[] dist; 
    	static boolean[] check; 
    	static List<Integer> resultList; 
        
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
    
    		int testcase = Integer.parseInt(br.readLine());
            
    		for(int i = 0; i < testcase; i++){
    			StringTokenizer st = new StringTokenizer(br.readLine()); 
    			V = Integer.parseInt(st.nextToken());
    			E = Integer.parseInt(st.nextToken());			
    			T = Integer.parseInt(st.nextToken());
    
    			// 그래프 배열 선언
    			graph = new int[V + 1][V + 1];
    			dist = new int[V + 1];
    			for(int j = 0; j < graph.length; j++)
    				Arrays.fill(graph[j], INF);
    			Arrays.fill(dist, INF);
    			check = new boolean[V + 1];
                
    			// s, g, h 초기화
    			st = new StringTokenizer(br.readLine()); 
    			start = Integer.parseInt(st.nextToken());
    			g = Integer.parseInt(st.nextToken());			
    			h = Integer.parseInt(st.nextToken());
                
    			// 그래프 정보 저장
    			for(int j = 0; j < E; j++){
    				st = new StringTokenizer(br.readLine()); 
    				int v1 = Integer.parseInt(st.nextToken());
    				int v2 = Integer.parseInt(st.nextToken());			
    				int distance = Integer.parseInt(st.nextToken());  
                    
    				graph[v1][v2] = graph[v2][v1] = distance * 2;
    			}
                
    			graph[h][g] = graph[g][h] = graph[h][g] - 1;
                
    			resultList = new ArrayList<>();
    			for(int j = 0; j < T; j++)
    				resultList.add(Integer.parseInt(br.readLine()));
    			dijkstra();
    			Collections.sort(resultList);
    			for(int num : resultList)
    				if(dist[num] % 2 == 1) bw.write(num + " ");
    			bw.write("\n");
    		}
        
    		bw.flush();
    		bw.close();
    		br.close();
    	}
    
    	public static void dijkstra() { 
    		PriorityQueue<Node> pqueue = new PriorityQueue<>();
    		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 (int i = 1; i <= V; i++) {
    					if(!check[i] && dist[i] > dist[cur] + graph[cur][i]){
    						dist[i] = dist[cur] + graph[cur][i];            
    						pqueue.offer(new Node(i, dist[i]));
    					}                             
    				}                
    			}
    		}
    	}
    }
  • Python
  • from heapq import heappush, heappop
    import sys
    
    # dijkstra 경로 탐색
    def dijkstra(start):
        dp = [100000000 for i in range(n + 1)]
        dp[start] = 0
        heap = []
        heappush(heap, [0, start])
        while heap:
            we, nu = heappop(heap)
            for ne, nw in graph[nu]:
                wei = we + nw
                if dp[ne] > wei:
                    dp[ne] = wei
                    heappush(heap, [wei, ne])
        return dp
    
    testcase = int(sys.stdin.readline())
    for _ in range(testcase):
        n, m, t = map(int, sys.stdin.readline().split())
        start, g, h = map(int, sys.stdin.readline().split())
        graph = [[] for i in range(n + 1)]
        dist = []
        for j in range(m):
            a, b, d = map(int, sys.stdin.readline().split())
            graph[a].append([b, d])
            graph[b].append([a, d])
        for k in range(t):
            dist.append(int(sys.stdin.readline()))
        start_ = dijkstra(start)
        g_ = dijkstra(g)
        h_ = dijkstra(h)
        resultlist = []
        for l in dist:
            if start_[g] + g_[h] + h_[l] == start_[l] or start_[h] + h_[g] + g_[l] == start_[l]:
                resultlist.append(l)
        resultlist.sort()
        for f in resultlist:
            print(f, end=' ')
        print()