<aside> 💛

시간 제한 : 1초, 난이도 : 골드 4, 백준 : 11404번

</aside>

dist[i][j] = 100001라고 썼다가 틀림 (무한대 수를 100001로 지정했다가 틀림)

• dist[i][j] = 10000001;로 고쳐서 맞았는데 왜일까?

dist[i][k] = 100000 dist[k][j] = 100000 ⇒ dist[i][k] + dist[k][j] = 200000 > 100001 ⇒ if 조건에 의해 잘못된 경로로 갱신됨

→ 따라서 100000 * 최대 도시 수 (100)보다 큰 수로 설정해야한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Practice61 {

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, M;
	static int dist[][];
	public static void main(String[] args) throws IOException{
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		dist = new int[N + 1][N + 1];
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				if(i == j)
					dist[i][j] = 0;
				else
					dist[i][j] = 10000001; 
			}
		}
		
		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			if(dist[s][e] > v)
				dist[s][e] = v;
		}
		
		for(int k = 1; k <= N; k++) {
			for(int i = 1; i <= N; i++) {
				for(int j = 1; j <= N; j++) {
					if(dist[i][j] > dist[i][k] + dist[k][j])
						dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				if(dist[i][j] == 10000001)
					System.out.print("0 ");
				else
					System.out.print(dist[i][j] + " ");
			}
			System.out.print("\\n");
		}		

	}

}