白俊-1719号速達

3406 ワード
ダエストラ テキストリンク
https://www.acmicpc.net/problem/1719


方法

  • 最短距離を求めるためArrayList<Point>[] ADJ配列を生成
  • アレイ双方向幹線接続
    2 Dアレイの場合は、n回のナビゲーションが必要で、アレイのリストサイズでナビゲートするだけで時間を節約できます.
  • ノードごとに複数の曲線をナビゲート
  • path[]アレイ記録現在のノードの前ノード
  • 出力時、現在のノード面-出力
    そうでない場合は、現在のノードで前のノードを検索し、終了ノードか前のノードかを確認します...繰返し出力

    • ソース

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static ArrayList<Point>[] ADJ;
	static int[][] ans;
	static int N, M;
	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());
		M = Integer.parseInt(st.nextToken());
		
		ADJ = new ArrayList[N+1];
		for(int i = 0; i < N+1; i++) {
			ADJ[i] = new ArrayList<Point>();
		}
		
		ans = new int[N+1][N+1];
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			ADJ[s].add(new Point(e, w));
			ADJ[e].add(new Point(s, w));
			
		}
		
		for(int i = 1; i < N+1; i++) {
			dijkstra(i);
		}
		
	}
	
	public static void dijkstra(int node) {
		int[] dist = new int[N+1];
		int[] path = new int[N+1];
		boolean[] visit = new boolean[N+1];
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[node] = 0;
		
		Queue<Point> q = new LinkedList<Point>();
		q.offer(new Point(node, 0));
		while(!q.isEmpty()) {
			Point cur = q.poll();
			int curNode = cur.node;
			int curWeight = cur.weight;
			
//			if(visit[curNode]) continue;
//			visit[curNode] = true;
			
			for(int i = 0; i < ADJ[curNode].size(); i++) {
				Point newNode = ADJ[curNode].get(i);
				
				if(dist[newNode.node] > curWeight + newNode.weight) {
					dist[newNode.node] = curWeight + newNode.weight;
					q.offer(new Point(newNode.node, curWeight + newNode.weight));
					path[newNode.node] = curNode == node ? newNode.node : curNode;
				}
			}
		}
		
		
		
		for(int i = 1; i < N+1; i++) {
			if(i == node) System.out.print("- ");
			else {
				int j = i;
				while(j != path[j]) {
					j = path[j];
				}
				System.out.print(j + " ");
			}
		}
		System.out.println();
	}

}
class Point{
	int node;
	int weight;
	
	Point(int node, int weight){
		this.node = node;
		this.weight = weight;
	}
}
    DataTableとソリッドオブジェクトの相互回転
    これがPython CHP 5の符号化テストです.DFS/BFS_2. ナビゲーションアルゴリズムDFS/BFS