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

「1125 Stockbroker Grapevine」の編集履歴(バックアップ)一覧はこちら

1125 Stockbroker Grapevine」の最新版変更点

追加された行は青色になります。

削除された行は赤色になります。

-
+**1125 Stockbroker Grapevine
+**問題
+http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
+**解答例
+ 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);
+             }
+         }
+     }
+ }
ツールボックス

下から選んでください:

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