华为oj：出差航班选择问题

【描述】小哒是x区域的销售经理，常驻5号城市，并且经常要到1、2、3、4、6号城市出差。当机场出现大雾的情况的时候，会导致对应城市的所有航班的起飞以及降落均停止（即不能从该城市出发，其他城市也不能到达该城市）。小哒希望知道如果他需要到X城市出差的时候，如果遇到Y城市出现大雾，他最短的飞行时间及飞行路径。注意：当两个城市不能到达的时候，消耗时间默认为1000

输入：1、2、3、4、6,小哒需要出差的城市 0、1、2、3、4、5、6，出现大雾的城市，其中0就是没有城市出现大雾

输出：最短到达的时间 [经过的城市]，以‘,’隔开

【思路】这条题目的核心在于

采用正常的索引，比如说1号城市就是1号，而不是数组中的0号，当需要在数组中去遍历搜索的时候责直接减一即可
采用数组来表示链表，就是这个path，path[i]就是想要到i号城市必须要直接经过的城市

import java.util.Scanner;

public class route {
    public static int MX = 1000;
    public static int map[][] = {
            {MX , 2 , 10 , 5, 3 ,MX},
            {MX, MX , 12, MX, MX , 10},
            {MX, MX, MX, MX, 7, MX},
            {2 , MX, MX, MX, 2, MX},
            {4, MX , MX ,1, MX, MX},
            {3, MX, 1, MX, 2, MX}
    };
    public static void dijistra(int start , int end ,int[] dist, int[] path ){
        int[] v = {0 , 0, 0, 0, 0, 0, 0}; //7个，希望以正常的方式遍历
        dist[start] = 0;
        path[start]= start;
        while (true){
            int u = MX , dmin = MX;
            for (int i = 1; i <= 6; i++) {
                if(v[i] ==0){
                    if(dist[i]<dmin){
                        dmin = dist[i];
                        u = i;
                    }
                }
            }
            if (dmin==MX || u ==end){
                break;
            }
            v[u] =1 ;
            for (int i = 1; i <= 6; i++) {
                if(dist[i] > dmin +map[u-1][i-1]){
                    dist[i] = dmin + map[u-1][i-1];
                    path[i] = u;
                }
            }
        }
    }
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int start = 5;
        int end = scanner.nextInt();
        int mix = scanner.nextInt(); //大雾的城市
        if(mix!=0){
            for (int i = 0; i < 6; i++) {
                map[mix-1][i] = MX;
                map[i][mix-1] = MX;
            }
        }

        int[] dist = {MX , MX, MX , MX , MX, MX, MX};
        int[] path = new int[7];
        dijistra(start , end , dist, path);
        System.out.println(dist[end]);
        if(dist[end] == MX){
            System.out.print("[]");
            return;
        }
        String out = "";
        int k = end;
        while (k!=start){
            out+=(k+" ");
            k = path[k];
        }

        out+=start;
        String[] output = out.split(" ");
        for (int i = output.length-1; i >=0 ; i --) {
            if(i == output.length-1 ){
                System.out.print("["+output[i]);
            }else if(i==0){
                System.out.print(", "+ output[i] + "]");
            }else {
                System.out.print(", "+output[i]);
            }
        }

    }
}

yooocen / dadaLearningBlogs

华为oj：出差航班选择问题 #28