import java.io.*;

public class AntsTrip {
    
    public static void main(String[] args) {        
       boolean r0,r1,r2;
       int m = 0 ,n = 0;//m個城市,n個螞蟻
       int city_map[][];//城市距離取1到21之間的數
       float  tl[][];//信息素初始值為城市路線個數的倒數
       int ants_trip[][];//所有螞蟻行走路線
       int min_count;//當前最短路徑長
       int ant_count[];//記錄當前路徑長
       int min_trip[];//當前最短路徑的路線
       int walk_num;//記錄當前步數
       float proba[];//用于暫時存放概率
       float probb[];//用于計算概率使用
       float count_proba ;//用于計算概率使用
       float prob;//用于產生隨機概率
       int now_city ;//螞蟻當前所在城市    
       int next_city;//暫時記錄下一個城市
       
       r0=true;    
       while(r0){
           r0=false;
           try{
               BufferedReader in = new BufferedReader(
                   new InputStreamReader(System.in));
               System.out.print("請輸入城市的個數(整數):");
                String num_m =  in.readLine();
                System.out.print("請輸入螞蟻個數(整數):");
               String num_n =     in.readLine();                  
               m = Integer.parseInt( num_m );
              n = Integer.parseInt( num_n );                  
              if(m <= 0 && n <= 0){
                  System.out.print("輸入錯誤請從新輸入!\n");
                  r0 = true;
              }
           }catch(NumberFormatException e1){
               System.out.print("輸入錯誤請從新輸入!\n");
               r0 = true;
           }catch(IOException e2){
               System.out.print("輸入錯誤請從新輸入!\n");
               r0 = true; 
            }
       }//結束while(r0)得到城市的個數n 和螞蟻的個數m
       
        // TODO Auto-generated method stub        
        city_map = new int[m][m];
        tl = new float[m][m];
        min_trip = new int[m];
        ants_trip = new int[m][n];
        min_count=21*m;//因為城市之間有m個路段,每段最大取21
        proba = new float[m];
        probb = new float[m];
        ant_count = new int[n];
        
        System.out.print("產生的隨機地圖為:\n");
        for(int i=0; i<city_map.length; i++){
            for(int j=0; j<city_map.length; j++){
                if(i!=j){
                    city_map[j] = (int)(Math.random()*20)+1;//初始化城市
                    tl[j] = (float)1.0/m*(m-1);//初始化信息素
                    System.out.print("  c_map[" + i + "][" + j + "]" +"="+ city_map[j]);                    
                }
            }
            System.out.print("\n");
        }
        walk_num = 0;
        int marks0 = 0;//標記總循環次數
        boolean marks1;//標記是否都走同一路徑
        r2=true;
        while(r2){//總循環－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－步驟３
            marks0++;
            marks1 = true;
            for(int i=0; i<ants_trip.length; i++){//清空ants_trip
                for(int j=0; j<ants_trip[0].length; j++){
                    ants_trip[j] = 0;
                }
            }
            
            for(int j=0; j<ants_trip[0].length; j++){//把n只螞蟻(行)放入m個城市(列)中
                int k;
                k = (int)(Math.random()*m);
                ants_trip[k][j]=1;
            }
            
            for(int j=0; j<ants_trip[0].length;j++){//螞蟻循環 -----------------------------步驟1
                int k1=0;
                now_city = 0;
                ant_count[j] = 0;
                for(int i=0; i<ants_trip.length; i++){//找到螞蟻的出發城市
                    if(ants_trip[j] == 1){
                        k1 = i;
                        now_city = i;
                        walk_num = 1;
                        break;
                    }                    
                }
                r1 = true;
                while( r1 ){//用于處理單只螞蟻j
                    r1 = false;
                    count_proba = 0;
                    prob = 0;                    
                    for(int i=0; i<proba.length; i++){
                        proba=0;//將概率暫存表清空
                        probb=0;
                    }
                    
                    for(int i=0; i<ants_trip.length; i++){//計算由now_city到其他城市的概率
                        if(ants_trip[j]==0){
                            proba=(float)(tl[now_city]*(1.0/city_map[now_city]))*100000;
                        }
                    }
                                       
                    for(int i=0,k=0; i<proba.length; i++){//將概率處理為線段
                        if(proba != 0){
                            count_proba += proba;
                            probb[k] = count_proba;                                 
                            k++;                            
                        }
                    }
                    next_city = 0;
                    prob = (float)Math.random()*count_proba;//產生隨機概率                    
                    
                    for(int i=0,l=0; i<probb.length; i++){//判斷落入區間
                        if(prob < probb){
                            
                            for(int k=0; k<proba.length; k++)
                            {
                                if(proba[k]!=0){
                                    l++;
                                }
                                if(l==i+1){
                                    next_city = k;//得到了下一個城市
                                    break;
                                }
                            }
                            break;
                        }
                    }//結束了對落入范圍的判斷，獲得了下一個城市
                    ant_count[j] +=city_map[now_city][next_city];                        
                    now_city = next_city;                
                    walk_num++;
                    ants_trip[now_city][j] = walk_num;
                    
                    int k3,k4;//                    判斷螞蟻j是否走完所有城市
                    k3 = 0; k4 = 0;
                    for(int i=0; i<ants_trip.length; i++){
                        if(ants_trip[j]==0){
                            k3++;k4=i;
                        }
                    }
                    if(k3>1){
                        r1=true;
                    }else{
                        ants_trip[k4][j]=m;
                        ant_count[j] += city_map[now_city][k4];
                        ant_count[j] += city_map[k4][k1];//由最后一個城市回到出發城市
                        now_city = k4;
                        System.out.print("\n  螞蟻" + j + "走完全程,總路程為" + ant_count[j]);
                    }                                       
               }//結束了while語句，即一只螞蟻j已經走完所有城市    
                
                /*int k6 = 1;
               while(k6 <= m){
                   for(int i=0; i<ants_trip.length; i++){
                       if(ants_trip[j]==k6){
                           System.out.print("  "+i);
                       }
                   }
                   k6++;
               }*/
               if(ant_count[j] < min_count){
                for(int i=0; i<ants_trip.length; i++){
                    min_trip=ants_trip[j];                            
                }
                min_count = ant_count[j];
               }
               System.out.print("\n  當前最短路程長為"+ min_count);                        
            } ////////////////////////所有螞蟻都走過了            
            System.out.print("\n所有螞蟻都走完所有城市!");
            
            for(int i=0; i<tl.length; i++){//－－－－－－－－－－－－－－－－步驟２
                for(int j=0; j<tl[0].length; j++){
                    tl[j] /=4;
                }
            }
            for(int j=0; j<ants_trip[0].length; j++){
                for(int i=0; i<tl.length; i++){
                    for(int k=0; k<ants_trip.length; k++){
                        if((ants_trip[j]-1)==ants_trip[k][j]%m){
                            tl[k] +=(float) 3.0/(8*ant_count[j]);
                               if((min_trip-1)==min_trip[k]%m){
                                         tl[k] +=(float) 3.0/(8*min_count);                          
                                       }                          
                        
                        }
                    }
                }
            }
            for(int j=0,k=0; j<ants_trip[0].length; j++){//判斷所有螞蟻是否都走同一路線
                for(int i=0; i<ants_trip.length; i++){                    
                    k=ants_trip[0][j]-min_trip[0];
                    if((ants_trip[j]-k-1+m)%m != (min_trip-1)){
                        marks1 = false;
                        j = ants_trip[0].length;
                        break;
                    }
                }
            }
            if(marks1 || marks0 > 100){//循環次數最高為100次
                if(marks1){
                    System.out.print("\n\n\n成功查尋到最短路!!");
                }
                else{
                    System.out.print("\n\n\n循環到次數了!");
                }
                r2=false;
                }
        }//結束總while        
        System.out.print("\n當前路線為：");
        int k5 = 1;
        while(k5 <= m){
           for(int i=0; i<min_trip.length; i++){
               if(min_trip==k5){
                   System.out.print(i+"  ");
               }
           }
           k5++;
       }
            
        System.out.print("\n總路程為：" + min_count);    
        System.exit(0);
    }//結束main
}