Aizu Online Judge 0189 Convenient Location

■0189 Convenient Location

各々のノードのついて，Dijkstraをやるだけ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  LinkedList<E>[] es;  
18.   
19.  @SuppressWarnings("unchecked")  
20.  void run(){  
21.   for(;;){  
22.    es=new LinkedList[10];  
23.    for(int i=0; i<es.length; i++){  
24.     es[i]=new LinkedList<E>();  
25.    }  
26.    n=0;  
27.    m=sc.nextInt();  
28.    if(m==0){  
29.     break;  
30.    }  
31.    for(int i=0; i<m; i++){  
32.     int u=sc.nextInt();  
33.     int v=sc.nextInt();  
34.     int w=sc.nextInt();  
35.     es[u].add(new E(v, w));  
36.     es[v].add(new E(u, w));  
37.     n=max(n, u+1);  
38.     n=max(n, v+1);  
39.    }  
40.    solve();  
41.   }  
42.  }  
43.   
44.  void solve(){  
45.   int min=INF;  
46.   int v=0;  
47.   for(int i=0; i<n; i++){  
48.    int d=dijkstra(i);  
49.    if(d<min){  
50.     v=i;  
51.     min=d;  
52.    }  
53.   }  
54.   println(v+" "+min);  
55.  }  
56.   
57.  int dijkstra(int s){  
58.   int[] d=new int[n];  
59.   PriorityQueue<P> que=new PriorityQueue<P>();  
60.   
61.   Arrays.fill(d, INF);  
62.   d[s]=0;  
63.   que.offer(new P(s, 0));  
64.   for(; !que.isEmpty();){  
65.    P p=que.poll();  
66.    if(d[p.v]<p.d){  
67.     continue;  
68.    }  
69.    for(E e : es[p.v]){  
70.     if(d[e.to]>d[p.v]+e.cost){  
71.      d[e.to]=d[p.v]+e.cost;  
72.      que.offer(new P(e.to, d[e.to]));  
73.     }  
74.    }  
75.   }  
76.   
77.   int res=0;  
78.   for(int i=0; i<n; i++){  
79.    res+=d[i];  
80.   }  
81.   return res;  
82.  }  
83.   
84.  class E{  
85.   int to, cost;  
86.   
87.   E(int to, int cost){  
88.    this.to=to;  
89.    this.cost=cost;  
90.   }  
91.  }  
92.   
93.  class P implements Comparable<P>{  
94.   int v, d;  
95.   
96.   P(int v, int d){  
97.    this.v=v;  
98.    this.d=d;  
99.   }  
100.   
101.   @Override  
102.   public int compareTo(P p){  
103.    return d-p.d;  
104.   }  
105.  }  
106.   
107.  void debug(Object... os){  
108.   System.err.println(Arrays.deepToString(os));  
109.  }  
110.   
111.  void print(String s){  
112.   System.out.print(s);  
113.  }  
114.   
115.  void println(String s){  
116.   System.out.println(s);  
117.  }  
118.   
119.  public static void main(String[] args){  
120.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
121.   new Main().run();  
122.  }  
123. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   es=new LinkedList[10];
   for(int i=0; i<es.length; i++){
    es[i]=new LinkedList<E>();
   }
   n=0;
   m=sc.nextInt();
   if(m==0){
    break;
   }
   for(int i=0; i<m; i++){
    int u=sc.nextInt();
    int v=sc.nextInt();
    int w=sc.nextInt();
    es[u].add(new E(v, w));
    es[v].add(new E(u, w));
    n=max(n, u+1);
    n=max(n, v+1);
   }
   solve();
  }
 }

 void solve(){
  int min=INF;
  int v=0;
  for(int i=0; i<n; i++){
   int d=dijkstra(i);
   if(d<min){
    v=i;
    min=d;
   }
  }
  println(v+" "+min);
 }

 int dijkstra(int s){
  int[] d=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  d[s]=0;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }

  int res=0;
  for(int i=0; i<n; i++){
   res+=d[i];
  }
  return res;
 }

 class E{
  int to, cost;

  E(int to, int cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v, d;

  P(int v, int d){
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}