Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- import java.io.PrintWriter;
- import static javafx.scene.input.KeyCode.V;
- /**
- * Created by Сергей on 27.05.2016.
- */
- public class Solution321 {
- public static void main(String Args[]){
- Scanner sc=new Scanner(System.in);
- PrintWriter printWriter = new PrintWriter(System.out);
- int vCount=sc.nextInt();
- // Граф будем хранить в матрице смежности
- int[][] D = new int[vCount][vCount];
- for (int i = 0; i < vCount; i++) {
- for (int j = 0; j < vCount; j++) {
- // Считываем вес ребра между ве
- // ршинами
- // i и j соответственно
- D[i][j] = sc.nextInt();
- if (D[i][j]==-1) D[i][j]=9999999;
- }
- }
- for (int i=0; i<vCount; i++) D[i][i]=0;
- // Согласно алгоритму будем обновлять
- // ответ для каждой пары вершин i и j,
- // перебирая промежуточную вершину k
- for (int k=0; k<vCount; k++)
- for (int i=0; i<vCount; i++)
- for (int j=0; j<vCount; j++)
- if (D[i][k]>0 && D[k][j]>0 && i!=j)
- if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
- D[i][j]=D[i][k]+D[k][j];
- for (int i = 0; i < vCount; i++) {
- for (int j = 0; j < vCount; j++){
- if (D[i][j]==9999999) D[i][j]=0;
- }
- }
- for (int i = 0; i < vCount; i++) {
- for (int j = 0; j < vCount; j++) {
- printWriter.print(D[i][j] + " ");
- }
- printWriter.println();
- }
- int max=0;
- for (int i = 0; i < vCount; i++) {
- for (int j = 0; j < vCount; j++) {
- if (max < D[i][j]) max = D[i][j];
- }
- }
- printWriter.println(max);
- // После выполнения программы необходимо закрыть
- // потоки ввода и вывода
- sc.close();
- printWriter.close();
- }
- }
Add Comment
Please, Sign In to add comment