Programming Challenge -PKU- 1125 Stockbroker Grapevine

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

1125 Stockbroker Grapevine

問題

解答例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0) break;
            
            int[][] dist = new int[n][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(i==j) dist[i][j] = 0;
                    else dist[i][j] = 65536;
                }
            }
            
            for(int i=0;i<n;i++){
                int m=sc.nextInt();
                for(int j=0;j<m;j++){
                    int p = sc.nextInt()-1;
                    int t = sc.nextInt();
                    dist[i][p] = t;
                }
            }
            
            int[][] a = new int[n][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    a[i][j] = dist[i][j];
                }
            }
                                                                                                                                                               
            for(int k=0;k<n;k++){
                for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++){
                        if(a[i][j]>a[i][k]+a[k][j]){
                            a[i][j] = a[i][k] + a[k][j];
                        }
                    }
                }
            }
            
            int retp = -1;
            int rett = 65536;
            for(int i=0;i<n;i++){
                int max = 0;
                for(int j=0;j<n;j++){
                    if(max<a[i][j]) max = a[i][j];
                }
                
                if(max<rett){
                    retp = i;
                    rett = max;
                }
            }
            
            if(retp==-1){
                System.out.println("disjoint");
            }
            else{
                System.out.println((retp+1)+" "+rett);
            }
        }
    }
}