阿里3.26笔试第二题——酒店的平均距离

package Algorithms.AL.AL010;

import java.util.Scanner;

/**
 * 题目描述
 *      三名理论计算机科学家计划前往威海旅行。 但是，他们无法就住宿达成共识，因为有些人喜欢某些酒店，
 *      而另一些人则喜欢其他酒店。 他们决定晚上住在不同的旅馆里，第二天在一个旅馆见面。
 *      他们见面的酒店不一定是他们入住的酒店之一。
 *      每对酒店之间都有一条特定长度的道路，每位理论计算机科学家都会在旅行开始之前准备好候选酒店列表。
 *      当他们到达威海时，他们每个人都会从候选酒店列表中统一独立地选择一家酒店。
 *      而且，他们将在一家酒店见面，以使他们的路线总长度最小化。
 *      作为理论计算机科学小组的成员，您能说出他们的路线的预期总长度吗？
 *
 * 输入描述
 *      输入的第一行包含一个整数 n（1≤ n ≤200000），表***海的酒店数量。
 *      接下来 n-1 行中的每行都包含三个整数 u，v，w（1≤u，v≤n，u≠v，1≤w≤1000），
 *      表示长度为 w 的道路，连接编号为 u 和 v 的旅馆。
 *      保证每对酒店之间都有一条独特的道路。
 *      输入的最后三行指定候选酒店列表，每位理论计算机科学家一行。
 *      每行有一个整数 m（1≤ m ≤n）和 m 个不同的整数 a1，a2，⋯，am（1≤ ai ≤n），这意味着候选酒店列表为编号为 a1，a2，⋯，的酒店。
 *
 * 输出描述
 *      输出所有情况下最短总路程的平均值
 *
 * 示例1
 *      输入
 *      3
 *      1 2 1
 *      2 3 2
 *      1 1
 *      1 2
 *      1 3
 *      输出
 *      3
 *
 * 示例2
 *      输入
 *      5
 *      1 2 3
 *      1 3 5
 *      2 4 7
 *      2 5 11
 *      3 2 4 5
 *      4 1 2 3 5
 *      2 1 3
 *      输出
 *      13.958333333333
 *
 */
public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            // 获取酒店数量
            int n = scanner.nextInt();
            // 构建酒店之间直接距离矩阵
            int[][] distances = new int[n][n];
            // 将直接距离初始化为 Integer.MAX_VALUE，表示各个酒店之间没有连接
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    distances[i][j] = Integer.MAX_VALUE;
                }
            }
            // 同一酒店与自己的距离当然为 0
            for (int i = 0; i < n; i++) {
                distances[i][i] = 0;
            }
            // 接下来 n-1 行，获取每两个酒店 u 和 v 之间的直接距离 w
            for (int i = 0; i < n-1; i++) {
                int u = scanner.nextInt()-1;
                int v = scanner.nextInt()-1;
                int w = scanner.nextInt();

                distances[u][v] = distances[v][u] = w;
            }
            // 利用 Floyed 算法计算每两个酒店之间的最短距离
            for (int t = 0; t < n; t++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (distances[i][t] < Integer.MAX_VALUE && distances[t][j] < Integer.MAX_VALUE
                            && distances[i][t] + distances[t][j] < distances[i][j]) {
                            distances[i][j] = distances[i][t] + distances[t][j];
                        }
                    }
                }
            }

            // 接下来获取三名科学家每个人喜欢的酒店编号
            // 第一名科学家喜欢的酒店数量
            int num1 = scanner.nextInt();
            // 第一名科学家喜欢的酒店编号
            int[] favorite1 = new int[num1];
            for (int i = 0; i < num1; i++) {
                favorite1[i] = scanner.nextInt()-1;
            }
            // 第二名科学家喜欢的酒店数量
            int num2 = scanner.nextInt();
            // 第二名科学家喜欢的酒店编号
            int[] favorite2 = new int[num2];
            for (int i = 0; i < num2; i++) {
                favorite2[i] = scanner.nextInt()-1;
            }
            // 第三名科学家喜欢的酒店数量
            int num3 = scanner.nextInt();
            // 第三名科学家喜欢的酒店编号
            int[] favorite3 = new int[num3];
            for (int i = 0; i < num3; i++) {
                favorite3[i] = scanner.nextInt()-1;
            }

            // 三名科学家一共有 num1*num2*num3 种不同组合
            int nums = num1*num2*num3;
            // 设置总路径
            int sum = 0;
            // 获取每种情况下的最短路径
            for (int i = 0; i < num1; i++) {
                for (int j = 0; j < num2; j++) {
                    for (int k = 0; k < num3; k++) {
                        // 计算最小值
                        int min = Integer.MAX_VALUE;
                        for (int v = 0; v < n; v++) {
                            min = Math.min(min, distances[favorite1[i]][v] + distances[favorite2[j]][v] + distances[favorite3[k]][v]);
                        }
                        sum += min;
                    }
                }
            }

            // 输出统计结果
            System.out.println(sum*1.0/nums);
        }
    }
}