[アルゴリズム]Java/バックアップ/FDD/1404
[アルゴリズム]Java/バックアップ/FDD/1404
質問する
質問リンク
方法
これはfloodとshallアルゴリズムを用いることができる基本的な例の問題である.
コード#コード#
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_11404 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] mat = new int[n+1][n+1];
final int INF = 10000001;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i!= j) mat[i][j] = INF;
}
}
for(int i=0;i<m;i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
mat[v1][v2] = Math.min(cost, mat[v1][v2]);
}
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
if(k==i) continue;
for(int j=1;j<=n;j++) {
if(k==j || i==j) continue;
mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(mat[i][j] == INF) mat[i][j] = 0;
System.out.print(mat[i][j]+" ");
}
System.out.println();
}
}
}
Reference
この問題について([アルゴリズム]Java/バックアップ/FDD/1404), 我々は、より多くの情報をここで見つけました https://velog.io/@gandi0330/알고리즘-Java-백준-플로이드-11404テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol