【单源最短路 选点】题解

题干信息解读
农场中有 n 块编号 1 至 n 的农田，农田间有 m 条双向道路。已知起点农田 p 的位置，以及各农田的完成状态（1 为完成，0 为未完成）。需要找到距离 p 最近且未完成的农田，若有多个则选编号最小的，若不存在则输出 0。

整体做题思路
本题通过朴素版 Dijkstra 算法求解单源最短路径，再筛选出符合条件的结果。具体步骤如下：
初始化邻接矩阵：用邻接矩阵存储农田间的道路距离，初始化为较大值（1e9），表示不可达。
读取完成状态：记录各农田是否完成（b 数组）。
处理道路信息：对于每条双向道路，更新邻接矩阵，保留最小距离（处理重边）。
计算最短路径：使用朴素 Dijkstra 算法计算起点 p 到所有农田的最短距离（适合 n≤2500 的规模）。
筛选结果：在未完成的农田中，找到距离 p 最近的；若距离相同，选择编号最小的；若不存在则输出 0。

题目中的难点和注意事项
邻接矩阵初始化：需将初始距离设为足够大的值（1e9），避免与实际道路距离冲突。
双向道路处理：每条道路需在邻接矩阵中双向更新，且保留最小距离（处理重边）。
Dijkstra 算法实现：每次需找到未访问节点中距离最小的，更新其邻接节点的距离。
结果筛选逻辑：需排除起点 p 本身（即使未完成），优先比较距离，距离相同时选编号小的。

AC代码（如有雷同，纯属巧合）（改编自@bong）

#include<bits/stdc++.h>
using namespace std;
int n,m,p;               // n:农田数，m:道路数，p:起点农田编号
bool b[2501];            // 存储农田完成状态（1:完成，0:未完成）
int a[2501][2501];       // 邻接矩阵，存储农田间的距离
int d[2501];             // 存储起点p到各农田的最短距离
bool v[2501];            // 标记农田是否已确定最短路径
int main(){
	cin>>n>>m>>p;
	// 初始化邻接矩阵为较大值（表示不可达）
	for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            a[i][j]=1e9;
    // 读取各农田的完成状态
    for(int i=1;i<=n;i++)cin>>b[i];
	// 初始化距离数组为较大值，起点p的距离设为0
	for(int i=0;i<=n;i++)d[i]=1e9;
	d[p]=0;
	// 读取道路信息，更新邻接矩阵（保留最小距离，处理双向道路）
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=a[y][x]=min(a[x][y],z);  // 双向道路，取最小距离
	}
    // 朴素Dijkstra算法计算最短路径
    for(int i=1;i<n;i++){  // 循环n-1次，确定n-1个节点的最短距离
		int x=0;  // 记录当前未访问且距离最小的节点
		for(int j=1;j<=n;j++)
			if(d[j]<d[x]&&!v[j])  // 找距离更小且未访问的节点
				x=j;
        v[x]=1;  // 标记该节点已确定最短路径
		// 更新邻接节点的距离（仅关注未完成的农田）
		for(int j=1;j<=n;j++)
			if(!b[j]&&a[x][j]!=1e9&&d[j]>d[x]+a[x][j])
				d[j]=d[x]+a[x][j];
	}
    // 筛选结果：找距离最近且未完成的农田（排除起点p）
    int x=0;
	for(int i=1;i<=n;i++)
		if(d[i]<d[x]&&!b[i]&&i!=p)  // 距离更小、未完成、不是起点
			x=i;
    cout<<x;  // 输出结果（若不存在则为0）
	return 0;
}

时间复杂度和空间复杂度
时间复杂度：
邻接矩阵初始化：O (n²)。
读取道路信息：O (m)。
朴素 Dijkstra 算法：O (n²)（外层循环 n 次，内层找最小值 O (n)，更新距离 O (n)）。
筛选结果：O (n)。
总时间复杂度：O (n² + m)，对于 n≤2500、m≤6500 的规模，完全可行。
空间复杂度：
邻接矩阵：O (n²)（存储 n×n 的距离信息）。
辅助数组（b、d、v）：O (n)。
总空间复杂度：O (n²)，适合 n≤2500 的规模。