题解

题目描述
给定一个救援物资集结点（编号为 $0$）和 $N$ 个受灾乡镇（编号为 $1$ 到 $N$），以及它们之间的距离矩阵。矩阵大小为 $(N+1)\times(N+1)$，其中元素 $d_{ij}$ 表示节点 $i$ 到节点 $j$ 的距离，不相邻时为 $0$。现在要求从节点 $0$ 到指定乡镇节点 $m$ 的最短路径长度。

思路
典型的单源最短路问题，可用 Dijkstra 算法 解决，适用于所有边权非负的情况。

1. 用数组 $\mathrm{dist}[\,]$ 记录从源点 $0$ 到各节点的最短距离，初始时
   
2. 用布尔数组 $\mathrm{vis}[\,]$ 标记已确定最短路的节点，初始均为 $\text{false}$。
3. 重复 $N+1$ 次：
   • 在所有 $\mathrm{vis}[i]=\text{false}$ 的节点中选取 $\mathrm{dist}[i]$ 最小者 $u$，将其标记为已访问：$\mathrm{vis}[u]=\text{true}$。
   • 对于每个与 $u$ 相邻且未访问的节点 $v$，若$$\mathrm{dist}[v]>\mathrm{dist}[u]+d_{u v},$$ 则更新$$\mathrm{dist}[v]=\mathrm{dist}[u]+d_{u v}.$$
4. 最终 $\mathrm{dist}[m]$ 即为所求最短路径长度。

时间复杂度：$O\bigl((N+1)^2\bigr)$，当 $N\le20$ 时完全可接受。

C++ 解法

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N; // 受灾乡镇个数
    int total = N + 1;
    vector<vector<int>> d(total, vector<int>(total));
    // 读入距离矩阵，节点 0 为物资集结点，1~N 为乡镇
    for (int i = 0; i < total; i++) {
        for (int j = 0; j < total; j++) {
            cin >> d[i][j];
        }
    }
    int m;
    cin >> m; // 目标乡镇编号

    const int INF = 1e9;
    vector<int> dist(total, INF);
    vector<bool> vis(total, false);

    dist[0] = 0; // 源点到自己的距离为 0

    // Dijkstra 算法主循环
    for (int i = 0; i < total; i++) {
        int u = -1, minDist = INF;
        // 找到未访问且 dist 最小的节点 u
        for (int j = 0; j < total; j++) {
            if (!vis[j] && dist[j] < minDist) {
                u = j;
                minDist = dist[j];
            }
        }
        if (u == -1) break; // 剩余节点不可达
        vis[u] = true;
        // 松弛以 u 为起点的所有边
        for (int v = 0; v < total; v++) {
            if (!vis[v] && d[u][v] > 0 && dist[v] > dist[u] + d[u][v]) {
                dist[v] = dist[u] + d[u][v];
            }
        }
    }

    cout << dist[m] << endl; // 输出从 0 到 m 的最短距离
    return 0;
}

Python 解法

import sys

def main():
    N = int(sys.stdin.readline().strip())  # 受灾乡镇个数
    total = N + 1
    # 读取距离矩阵
    d = [list(map(int, sys.stdin.readline().split())) for _ in range(total)]
    m = int(sys.stdin.readline().strip())  # 目标乡镇编号

    INF = 10**9
    dist = [INF] * total
    vis = [False] * total

    dist[0] = 0  # 源点到自己的距离为 0

    # Dijkstra 算法
    for _ in range(total):
        u = -1
        minDist = INF
        # 选出未访问的最小 dist 节点
        for i in range(total):
            if not vis[i] and dist[i] < minDist:
                u = i
                minDist = dist[i]
        if u == -1:
            break
        vis[u] = True
        # 松弛操作
        for v in range(total):
            if not vis[v] and d[u][v] > 0 and dist[v] > dist[u] + d[u][v]:
                dist[v] = dist[u] + d[u][v]

    print(dist[m])

if __name__ == "__main__":
    main()

Java 解法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 受灾乡镇个数
        int total = N + 1;
        int[][] d = new int[total][total];
        // 读取距离矩阵
        for (int i = 0; i < total; i++) {
            for (int j = 0; j < total; j++) {
                d[i][j] = sc.nextInt();
            }
        }
        int m = sc.nextInt(); // 目标乡镇编号

        final int INF = Integer.MAX_VALUE / 2;
        int[] dist = new int[total];
        boolean[] vis = new boolean[total];
        Arrays.fill(dist, INF);
        dist[0] = 0; // 源点到自己距离为 0

        // Dijkstra 算法
        for (int i = 0; i < total; i++) {
            int u = -1, minDist = INF;
            // 找到未访问且 dist 最小的节点 u
            for (int j = 0; j < total; j++) {
                if (!vis[j] && dist[j] < minDist) {
                    u = j;
                    minDist = dist[j];
                }
            }
            if (u == -1) break; // 剩余不可达
            vis[u] = true;
            // 对 u 的邻边进行松弛
            for (int v = 0; v < total; v++) {
                if (!vis[v] && d[u][v] > 0 && dist[v] > dist[u] + d[u][v]) {
                    dist[v] = dist[u] + d[u][v];
                }
            }
        }

        System.out.println(dist[m]); // 输出最短距离
    }
}

题目内容

某市发生地震，为了尽快将救援物质输送到受灾乡镇，需要你设计出从救援物质集结点(有仅有一个)到某一个受灾乡镇的最短线路

应急部门通过无人机助察了受灾地区地形，提供了各乡镇之间以及乡镇到救援物质集结点的距离，请你算出救援物质集结点到受灾多镇的最短路径。

输入描述

第一行，$N$，受灾乡镇个数,$3<=N<=20$

第二行至第$N+2$行，救援物质集结点以及各乡镇之间的货($N+1$个节点之间的相互距离短阵),距离取值范围是$[0,100]$、序号的节点表示救援物质集结点，序号$1-N$的节点表示各个受灾乡镇,$0$表示两个节点不相邻,

第$N+3$行，$m$，要抵达的乡镇序号(范围$1-N$)

输出描述

从物质集结点(节点$0$)到乡镇$m$(节点$m$)的最短路径长度

样例1

输入

5
0 5 13 0 0 0
5 0 12 0 75 0
13 12 0 25 0 0
0 0 25 0 35 20
0 75 0 35 0 40
0 0 0 20 40 0
3

输出

38

说明

从$0$到$3$的最短路径为$0-2-3$，长度为$13+25=38$

样例2

输入

5
0 5 13 0 0 0
5 0 12 0 75 0
13 12 0 25 0 0
0 0 25 0 35 20
0 75 0 35 0 40
0 0 0 20 40 0
5

输出

58

说明

从$0$到$5$的最短路径为$0-2-3-5$，长度为$13+25+20=58$