1125 Stockbroker Grapevine

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);
            }
        }
    }
}

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2006年04月16日 22:57
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。