[Algorithm] 😈スタンダード11404フロイド

0、問題

n(2≦n≦100)都市がある.ある都市から別の都市へのm(1≦m≦100000)シャトルバスもあります.バス1台につき1回の利用に必要な料金があります.
すべての都市の対(A,B)に対してプログラムを作成し,都市AからBまでの費用の最高値を求める.
入力
1列目は都市数n、2列目はバス数mです.次に、3行目からm+2行目まで、次のバスの情報を与えます.まず、最初にそのバスの出発都市番号をあげます.バスの情報は、バスの起点都市a、到着都市b、1回乗車に必要な料金cからなる.開始都市と到着都市は同じ状況ではない.費用が100000以下の自然数.
開始都市と到着都市を結ぶルートは1つだけではないかもしれません.
しゅつりょく
n行を出力します.i 1行目に出力されるj数字は、都市iからjまでの最小コストである.iからjへの出力ができない場合は、その位置で0を出力する.

1.アイデア

💡 floydとshallアルゴリズム
→すべての頂点間の最短距離を検索(n:m)
VS 1つの頂点からすべての頂点までの最短距離を検索する(1:n)
💡 直接接続ポイントのコストでアレイを挿入
💡 少しのコストを求めると、以前のコストに比べて、より少ない数で更新されます.

2.コア解答

1)直接接続された頂点のコストでアレイを挿入

for(int i=1; i<n+1; i++) {
	for(int j=1; j<n+1; j++) {
		if(i == j) 
			continue;
		arr[i][j] = INF;
	}
}

2)ワンポイントで料金を徴収した後、従来の料金よりも小額で更新

for(int mid=1; mid<n+1; mid++) {
	for(int start=1; start<n+1; start++) {
		for(int end=1; end<n+1; end++) {
			arr[start][end] = Math.min(arr[start][mid]+arr[mid][end], arr[start][end]);
		}
	}
}

3.コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Graph_2 {
	static int[][] arr;
	static int INF = 10000000;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		arr = new int[n+1][n+1];
		
		for(int i=1; i<n+1; i++) {
			for(int j=1; j<n+1; j++) {
				if(i == j) 
					continue;
				arr[i][j] = INF;
			}
		}
		
		for(int i=0; i<m; i++) {
			String[] s = br.readLine().split(" ");
			int start = Integer.parseInt(s[0]);
			int end = Integer.parseInt(s[1]);
			int cost = Integer.parseInt(s[2]);
			arr[start][end] = Math.min(cost,arr[start][end]);
		}
		
		for(int mid=1; mid<n+1; mid++) {
			for(int start=1; start<n+1; start++) {
				for(int end=1; end<n+1; end++) {
					arr[start][end] = Math.min(arr[start][mid]+arr[mid][end], arr[start][end]);
				}
			}
		}
		
		for(int i=1; i<n+1; i++) {
			for(int j=1; j<n+1; j++) {
				if(arr[i][j] >= INF)
					sb.append("0 ");
				else
					sb.append(arr[i][j]+" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}

}

4.結果

成功
(INF値をInteger.MAXVALUEとして位置付け、エラーを続行します.Integer.MAXVALUEに他の数値を追加する場合は考慮されません)😱)