package a;

import java.util.Arrays;

/**

 * 　　　　　　　　┏┓　　　┏┓+ +

 * 　　　　　　　┏┛┻━━━┛┻┓ + +

 * 　　　　　　　┃　　　　　　　┃

 * 　　　　　　　┃　　　━　　　┃ ++ + + +

 * 　　　　　　 ████━████ ┃+

 * 　　　　　　　┃　　　　　　　┃ +

 * 　　　　　　　┃　　　┻　　　┃

 * 　　　　　　　┃　　　　　　　┃ + +

 * 　　　　　　　┗━┓　　　┏━┛

 * 　　　　　　　　　┃　　　┃

 * 　　　　　　　　　┃　　　┃ + + + +

 * 　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting

 * 　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug

 * 　　　　　　　　　┃　　　┃

 * 　　　　　　　　　┃　　　┃　　+

 * 　　　　　　　　　┃　 　　┗━━━┓ + +

 * 　　　　　　　　　┃ 　　　　　　　┣┓

 * 　　　　　　　　　┃ 　　　　　　　┏┛

 * 　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +

 * 　　　　　　　　　　┃┫┫　┃┫┫

 * 　　　　　　　　　　┗┻┛　┗┻┛+ + + +

 *

 * @Author:Halburt

 * @Date:2019-04-24 下午 5:47

 * @Description:

 */

public class DijkstraDemo {

    //    表示无穷大 即不可达

    public static int NO_AIRPLANE = Integer.MAX_VALUE;

//    初始直飞价格表

    public int[][]  prices ;

    //    最优转机价格表

    public int[]   minPrice ;

    public boolean[] flag ;

    private int citySize;

    /**

     * @param citySize 城市数量

     */

    public DijkstraDemo(int citySize){

        this.citySize = citySize;

//      prices = new int [citySize][citySize];

        flag  =  new boolean [citySize - 1];

        minPrice = new int[citySize - 1 ];

    }

    public static int[][] getPrices(){

        int ZH = 0,SH = 1, BJ = 2, GZ = 3,CQ = 4,NJ = 5, HZ = 6,LS  = 7;

        int[][] prices =  new int[8][8];

        //from Zhuhai

        prices[ZH][CQ] = 1100;

        prices[ZH][SH] = 600;

        prices[ZH][BJ] = 900;

        prices[ZH][GZ] = 200;

        //others

        prices[CQ][NJ] = 400;

        prices[SH][CQ] = 400;

        prices[SH][BJ] = 500;

        prices[SH][NJ] = 200;

        prices[BJ][SH] = 400;

        prices[BJ][HZ] = 500 ;

        prices[BJ][LS] = 1400;

        prices[GZ][BJ] = 600 ;

        prices[GZ][LS] = 1500 ;

        prices[NJ][HZ] = 300 ;

        prices[HZ][SH] = 200 ;

        for(int i = 0 ; i < 8 ; i++){

            for(int j = 0 ; j < 8 ; j++){

                if(prices[i][j] == 0){

                    prices[i][j] =  NO_AIRPLANE;

                }

            }

        }

        return prices;

    }

    public static void main(String[] args) {

        DijkstraDemo demo = new DijkstraDemo(8);

        demo.dijkstra(getPrices());

    }

    public void dijkstra(int[][]  prices ){

        this.prices = prices;

//        初始化

//            初始化始发站价格表

        for(int i = 1; i < citySize;i++){

            minPrice[i-1] = prices[0][i];

        }

        System.out.println("初始化最优表：" + Arrays.toString(minPrice));

        dijkstra();

        System.out.println("最终最优价格表：" + Arrays.toString(minPrice));

    }

    private void dijkstra(){

        int min = Integer.MAX_VALUE;

        int minIdx = Integer.MAX_VALUE;

//        找到最小的价格

        for(int idx = 0 ; idx < minPrice.length ; idx ++ ) {

            if(!flag[idx] &&  minPrice[idx] < min ){

                min = minPrice[idx];

                minIdx =  idx ;

            }

        }//=已经没有最小的了

        if(minIdx == Integer.MAX_VALUE){

            return ;

        }

        //标记从该城市转机

        flag[minIdx] = true;

        minIdx += 1;

        System.out.println("转机城市序号"+minIdx +" 价格"+ minPrice[minIdx -1]);

       //获取该城市转机时飞往其他城市的价格表

        int cityPrice =  minPrice[minIdx -1];

        //获取杭州飞往该城市的价格

        int[] minCityPrices = prices[minIdx];

        for(int idx = 1 ; idx < citySize ; idx ++ ){

            int price = minCityPrices[idx];

//            如果从杭州到达该城市的价格 加上 idx城市转机的价格 低于  从杭州到达idx城市的价格 则更新

            if(!flag[idx -1 ] && price != NO_AIRPLANE  && (cityPrice+ price) < minPrice[idx - 1]){

//            可达的城市到达的

                minPrice[idx - 1] = cityPrice+ price;

                System.out.println(idx+"更新最优表：" + Arrays.toString(minPrice));

            }

        }

        dijkstra();

    }

}