白峻11404号.
https://www.acmicpc.net/problem/11404

質問する

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を出力する.

考える

解の時に白旗を一度聞いたが、INFは何度修正したか分からないので
最初の問題は100000未満または同じ自然数です.INFを100001に設定し、98%が「エラー」を続行します.出てきて、また修正しました.
その後INFをInteger.MAX_VALUE;に設定し、驚くべき結果値を得た.

こんな結果になって、私はここで最初は間違いだと思っていました.
何のバグだ...int正の整数の最高値を超えた結果を出力するだけです.
int音の整数Integer.MIN_VALUEに戻りました...

アクション

以前解答した問題はFloyd-Warshallアルゴリズムの試みで,探索だけなら
この問題は真のFloyd-Warshallアルゴリズムそのものである.
これは探索中に重み値が低いと更新されるという問題である.Road_Finder()関数を実行し、floodアルゴリズムを実行します.
ナビゲーションプロセス全体において、map[i][k]およびmap[j][k]を接続することができる.
すなわち、kで接続されると、map[i][j]の値がmap[i][k] + map[k][j]の値に置き換えられる.
ここで、既存のmap[i][j]の値が新しいmap[i][k] + map[k][j]の値より大きい場合、map[i][j]の値が更新される.
この手順を繰り返し、mapの配列を完了します.
次の出力では、移動できない位置を0とマークする必要があります.map[i][j] == INFであればmap[i][j] == 0で出力され、正解が得られる.

TMI

アルゴリズムを学ぶたびに感じるけど.
特にありません.長い間シャベルを使っていたので、一番時間を無駄にしたようです.

コード#コード#

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

public class Main {
	static StringBuilder sb;

	static final int INF = 1000000000;
	static int N, M;
	static int x = 0;
	static int y = 0;
	static int map[][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		map = new int[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = INF;

				if(i == j) {
					map[i][j] = 0;
				}
			}
		}

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());

			y = Integer.parseInt(st.nextToken()) - 1;
			x = Integer.parseInt(st.nextToken()) - 1;
			int value = Integer.parseInt(st.nextToken());

			map[y][x] = Math.min(map[y][x], value);
		}

		Road_Finder();

		sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
            	if(map[i][j] == INF) {
            		map[i][j] = 0;
            	}

                sb.append(map[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
	} // End of Main

	static void Road_Finder() {

		for(int k=0; k<N; k++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {

					if(map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
					}
					

				} // for(j) of End
			} // for(i) of End
		} // for(k) of End

	} // End of Find_Road

} // End of class