白準-11779回の最低コスト2を獲得

4082 ワード
dijkstra テキストリンク
https://www.acmicpc.net/problem/11779

方法


基本的なマルチアウトプットアルゴリズムGRAPH配列は、開始点インデックスに宛先と重みをノード形式で含み、入力された開始点と終了点を関数の開始点とする.dirは、インデックスに到達したときの開始インデックスを格納する配列である.キューに指定した時間と同じように、ウェイトが最小の場合にのみリフレッシュされます.
  • 優先キューを使用してタイムアウトしない
  • if(weight[cur.index] < cur.weight) continueを使用して、現在の重み付け比較を行い、時間を節約します.この線は既存のDaestraで作ったものではないと思います
  • 最小コストweightアレイ値を出力するだけでよいし、アクセスが必要な都市順序stackを出力し、サイト到着と移動経路を出発地にプッシュし、順次出力をポップアップすれば
    • を完了する

    ソース

    import java.util.*;
import java.io.*;
public class Main {
	static int N;
	static int M;
	static ArrayList<Node>[] GRAPH;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		GRAPH = new ArrayList[N+1];
		
		for(int i = 0; i < GRAPH.length; i++) {
			GRAPH[i] = new ArrayList<Node>();
		}
		
		for(int i = 0; i < M; i ++) {
			st = new StringTokenizer(br.readLine());
			int sp = Integer.parseInt(st.nextToken());
			int ep = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			GRAPH[sp].add(new Node(ep, weight));
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		dijkstra(start, end);
	}
	static void dijkstra(int s, int e) {
		int[] weight = new int[N+1];
		int[] dir = new int[N+1];
		Arrays.fill(weight, Integer.MAX_VALUE);
		weight[s] = 0;
		PriorityQueue<Node> q = new PriorityQueue<Node>();
		q.offer(new Node(s, 0));
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(weight[cur.index] < cur.weight) continue;
			
			for(int i = 0; i < GRAPH[cur.index].size(); i++) {
				Node link = GRAPH[cur.index].get(i);
				if(weight[link.index] > cur.weight + link.weight) {
					weight[link.index] = cur.weight + link.weight;
					dir[link.index] = cur.index;
					q.offer(new Node(link.index, cur.weight + link.weight));
				}
			}
		}
		Stack<Integer> stack = new Stack<Integer>();
		int iter = e;
		while(true) {
			stack.push(iter);
			if(dir[iter] == s) {
				stack.push(s);
				break;				
			} else {
				iter = dir[iter];
			}
		}		
		
		//1. 최소비용, 2. 경로에 있는 도시 개수, 3.방문한 도시 순서(출발지 도착지 포함)
		System.out.println(weight[e]);
		System.out.println(stack.size());
		while(!stack.isEmpty()) {
			System.out.print(stack.pop() + " ");
		}
	}
}

class Node implements Comparable<Node>{
	int index;
	int weight;
	Node(int index, int weight){
		this.index = index;
		this.weight = weight;
	}
	@Override
	public int compareTo(Node o) {
		return this.weight - o.weight;
	}	
}
    PAT (Advanced Level) Practise 1099 Build A Binary Search Tree (30)
    Django tutorial 2.