题解 | 郊区春游

function solve() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
        terminal: false
    });

    let lines = [];
    rl.on('line', (line) => {
        lines.push(line.trim());
    });

    rl.on('close', () => {
        let idx = 0;
        const [n, m, R] = lines[idx++].split(' ').map(Number);
        const target = lines[idx++].split(' ').map(Number); // 需游玩的R个郊区（1-based）
        const INF = 1e18;

        // 步骤1：映射目标郊区到0~R-1的索引
        const idxMap = new Map();
        target.forEach((v, i) => idxMap.set(v, i));
        const k = R; // 简化变量名

        // 步骤2：初始化Floyd-Warshall距离矩阵（1-based索引，n≤200）
        const dist = Array.from({ length: n + 1 }, () => Array(n + 1).fill(INF));
        for (let i = 1; i <= n; i++) dist[i][i] = 0; // 自身距离为0

        // 读取道路并更新距离矩阵
        for (let i = 0; i < m; i++) {
            const [a, b, c] = lines[idx++].split(' ').map(Number);
            if (c < dist[a][b]) { // 无重边，直接更新
                dist[a][b] = c;
                dist[b][a] = c;
            }
        }

        // 步骤3：Floyd-Warshall算法求多源最短路
        for (let k = 1; k <= n; k++) {
            for (let i = 1; i <= n; i++) {
                for (let j = 1; j <= n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 步骤4：提取目标郊区之间的最短路矩阵（0~R-1索引）
        const targetDist = Array.from({ length: k }, () => Array(k).fill(INF));
        for (let i = 0; i < k; i++) {
            for (let j = 0; j < k; j++) {
                const u = target[i];
                const v = target[j];
                targetDist[i][j] = dist[u][v];
            }
        }

        // 步骤5：状态压缩DP
        const fullMask = (1 << k) - 1;
        const dp = Array.from({ length: 1 << k }, () => Array(k).fill(INF));

        // 初始化：单个郊区的状态（费用0）
        for (let u = 0; u < k; u++) {
            dp[1 << u][u] = 0;
        }

        // 状态转移：按mask中1的个数递增遍历
        for (let mask = 1; mask < fullMask; mask++) {
            for (let u = 0; u < k; u++) {
                if (!(mask & (1 << u))) continue; // u不在当前集合，跳过
                if (dp[mask][u] === INF) continue; // 该状态不可达，跳过

                // 枚举未游玩的郊区v
                for (let v = 0; v < k; v++) {
                    if (mask & (1 << v)) continue; // v已游玩，跳过
                    const newMask = mask | (1 << v);
                    // 更新最小费用
                    if (dp[newMask][v] > dp[mask][u] + targetDist[u][v]) {
                        dp[newMask][v] = dp[mask][u] + targetDist[u][v];
                    }
                }
            }
        }

        // 步骤6：找到最小总费用（游玩完所有R个郊区的最小费用）
        let minCost = INF;
        for (let u = 0; u < k; u++) {
            if (dp[fullMask][u] < minCost) {
                minCost = dp[fullMask][u];
            }
        }

        console.log(minCost);
    });
}

solve();