import java.io.*;
 

 class Station  {              //station 클래스 선언!   (클래스와 객체 개념을 이용합니다..!)
   String station_name;  // 역이름
   int station_num;      // 역번호         
     
   Station(int num, String name) {                  //Station의 생성자 메소드 선언.
     station_num = num;
     station_name = name;
   }
 }

 class Subway{       
   String start_enter;
   String end_enter;
   static int start = 0;
   static int end = 0;
 }
 
 public class Station_line extends Subway  {               //  메인클래스..!  subway 상속시키기!
   public static void main(String [] args) {
   
     int m = 10000;           //null값 역할을 하는 m 선언
    int s,e;                 //입력값 받아올 s,e
    int i,j,k=0;
    float min;         //카운터 i,j,k 선언하기       for문에서 이용할 min값 사용 (= m값이 null값으로 쓸 쑤 잇게 하기..!)
    int [] v = new int[40];   //v[]선언 하기. data배열에서  열이 계산 됫는지 안됫는지 유무 파악하는 기능 배열
    float [] distance = new float[40]; //distance[]선언하기. 실제 거리 배열
    int [] via = new int[40]; 
    float [][] data = {
      {0,2.5f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {2.5f,0,3.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,3.0f,0,6.6f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,6.6f,0,8.2f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,8.2f,0,1.6f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,1.6f,0,2.5f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,2.5f,0,3.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,3,0,2.3f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,2.3f,0,1.4f,1.6f,1.2f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,1.4f,0,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,1.6f,m,0,m,m,2.6f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,1.2f,m,m,0,m,m,3.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,0,2.2f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,2.6f,m,2.2f,0,1.4f,m,m,m,m,m,m,2.1f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,3.0f,m,1.4f,0,2.8f,m,m,m,m,m,m,2.4f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.8f,0,1.4f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.4f,0,1.5f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.5f,0,2.7f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.7f,0,1.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.0f,0,2.4f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.4f,0,m,m,m,m,m,m,m,m,m,m,0.6f,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,2.1f,m,m,m,m,m,m,m,0,m,m,2.1f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.4f,m,m,m,m,m,m,m,0,m,m,m,2.2f,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0,0.7f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.7f,0,0.9f,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.1f,m,m,0.9f,0,0.8f,m,m,m,m,m,0.9f,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.2f,m,m,0.8f,0,1.8f,m,m,m,m,m,1.4f,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.8f,0,2.2f,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.2f,0,0.8f,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.8f,0,1.7f,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.7f,0,0.9f,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.6f,m,m,m,m,m,m,m,m,m,0.9f,0,m,m,m,m,m,m,m,0.7f},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.9f,m,m,m,m,m,m,0,m,0.9f,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.4f,m,m,m,m,m,m,0,m,0.8f,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.9f,m,0,m,1.0f,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.8f,m,0,m,0.8f,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.0f,m,0,2.6f,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.8f,2.6f,0,1.4f,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.4f,0,1.9f},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.7f,m,m,m,m,m,m,1.9f,0},
    };                          
    String[] names = new String[40] ;
   names[0] = "계양";
   names[1] = "귤현"; 
   names[2] = "박촌"; 
   names[3] = "임학";
   names[4] = "계산"; 
   names[5] = "경인교대입구"; 
   names[6] = "작전"; 
   names[7] = "갈산"; 
   names[8] = "부평구청"; 
   names[9] = "부평시장"; 
   names[10] = "부평"; 
   names[11] = "동수"; 
   names[12] = "부평삼거리"; 
   names[13] = "간석오거리"; 
   names[14] = "인천시청"; 
   names[15] = "예술회관"; 
   names[16] = "인천터미널"; 
   names[17] = "문학경기장"; 
   names[18] = "선학"; 
   names[19] = "신연수"; 
   names[20] = "원인재"; 
   names[21] = "동춘"; 
   names[22] = "동막";
   names[23] = "일";
   names[24] = "이";
   names[25] = "삼";
   names[26] = "사";
   names[27] = "오";
   names[28] = "육";
   names[29] = "칠";
   names[30] = "팔";
   names[31] = "구";
   names[32] = "십";
   names[33] = "십일";
   names[34] = "십이";
   names[35] = "십삼";
   names[36] = "십사";
   names[37] = "십오";
   names[38] = "십육";
   names[39] = "십칠";
   
   Station[] stations = new Station[40] ;
   
   for(i=0;i<40;i++) {
     stations[i] = new Station(i,names[i]);                     //http://ddogani.blog.me/50083572952 객체배열 감사합니다.
   
   
   BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));     //bufferedReader 클래스의 사용.( 입력 스트림)
    System.out.print(" 출발역을 입력하세욧! : ");
    start_enter = br.readLine()  ;
    for(i=0;i<40;i++) {
    if(start_enter.equals(stations[i].station_name)) {
      start = i;
    };
    }
    
    System.out.print(" 도착역을 입력하세욧! : "); 
    end_enter = br.readLine();
    for(j=0;j<40;j++) {
      if(end_enter.equals(stations[j].station_name)) {
        end = j;
      };
    }
                                                      // start,end 값에 입력값 받기.
       
      
        
    
    for( j=0; j<8; j++ ) { 
      v[j] = 0;  
      distance[j] = m;
    }                                            //초기화하기
    
    distance[start] = 0;                           // 자기 자신과의 역거리는 0이므로 0으로 선언한다..!
    
    
    for( i=0; i<8; i++ ) { 
      min = m;  
      for( j=0; j<8; j++ ) {  
        if( v[j] == 0 && distance[j] < min ) {    //v[]의 역할은 그 열이  실행됬으면 다시하지 않는 역할.
          k = j; 
          min = distance[j];                                
        }                                            //data[][] 에서 s지점 구하기.
      }                                           //distance가 s값을 받으면서 자기 자신의 위치 '0'을 사용 함으로써 자기 자신의 위치를 처음에
                                                   //
      v[k] = 1;                                       //  그래서 여기에 1을 넣어 줌으로써 안한 0 을 다시 for문 돌면서 처리 하는거지
      if(min==m) break;    // 
      
      for(j=0; j<8; j++) {   
        if(distance[j] > distance[k] + data[k][j]) {   //data[k][j]의 의미는 k번 역에서 j번 역으로 가는  거리임...! 즉 distance[j]는 null값 역할을 하는
          distance[j] = distance[k] + data[k][j];     via[j]=k;    //m에 v[]값을 이용해 구해진 k열에그리고 ditance[k]는 0임 언제나..!자기자신임..!
        }                                           // s가 있는 행의 배열 구하기.   distance[] s가 있는 행의 배열이 되는거지                                                  //= 이말이 뭘 뜻하는 거냐면,   1번에서 갈 수 있는 역을  말하는 거지.
      } 
    }  // 이거 i있는 포문에  끝이여.  i의 역할은 s역에서 ?역까지   반복문으로 다하 는거야  초기값은  위치찾고  다음에는 1역 2역...순서대로 찾는거지.
       // 이 for문은 i가 7까지 돌면서 시작점에서 을 찾아서 넣고, v[]값을 이용해서 차례차례  그 열에 해당하는 distance를 구하는 방법...!
    System.out.printf("\n %d에서 출발하여, %d로 가는  최단 시간은   %d입니다.\n", s, e, distance[e-1]);  
    
    
    int path[] = new int[40];  
    int path_cnt=0; 
    k=e-1; 
    while(true) {                       //무한 루프 선언.
      path[path_cnt++]=k; 
      if(k==s-1)break;                    //끝점과 시작점이 같다면 필요없겟지.
      k=via[k];                             //via[]은 i를 받아오는 거잔아  거기 까지 몇번 돌았는지를 확인하는 배열이야.

    }  
    System.out.print(" 경로는 : "); 
    for(i=path_cnt-1;i>=1;i--) { 
      System.out.printf("%d -> ",path[i]+1); 
    }  
    System.out.printf("%d입니다",path[i]+1); 
   }
   }
 }