题解

题意分析

题目要求在一个城市的路口网络中，选择一个最优位置新建一个消防站，使得所有路口到最近消防站的最大距离最小化。现有$f$个消防站分布在部分路口，城市共有$i$个路口，通过双向道路连接。目标是找到一个路口作为新消防站的位置，使得最远居民路口到最近消防站的距离最小。

解题思路

1. 图模型建立：将城市的路口和道路建模为无向图，路口为节点，道路为边，边权为道路长度。
2. 最短路径计算：使用Floyd算法计算所有路口之间的最短路径。
3. 现有消防站影响：计算每个路口到现有消防站的最短距离。
4. 最优位置选择：枚举每个可能的新消防站位置，计算添加该消防站后所有路口到最近消防站的最大距离，选择使该最大距离最小的路口。

实现步骤

1. 输入处理：读取现有消防站的位置和道路信息。
2. 初始化邻接矩阵：初始化图的邻接矩阵，节点自身距离为$0$，其他为无穷大$INF$。
3. Floyd算法：计算所有节点之间的最短路径。
4. 计算现有消防站的最短距离：对于每个路口，计算其到所有现有消防站的最短距离。
5. 枚举新消防站位置：对于每个可能的新消防站位置，计算添加后所有路口到最近消防站的最大距离，选择最优位置。
6. 输出结果：输出最优路口编号。

代码注释

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=600;      // 最大路口数量
const int INF=99999999;   // 表示无穷大
int e[maxn][maxn];        // 邻接矩阵，存储路口间的最短距离
int book[maxn];           // 标记现有消防站的位置
int ans[maxn];            // 存储每个路口到最近消防站的距离
int m;                    // 路口数量

void Floyd() {
    int i, j, k;
    for(k=1; k<=m; k++)   // 中间节点
        for(i=1; i<=m; i++)
            for(j=1; j<=m; j++)
                if(e[i][j] > e[i][k]+e[k][j]) // 松弛操作
                    e[i][j] = e[i][k]+e[k][j];
}

int main() {
    int f, t1, i, j, t2, t3, t4;
    while(scanf("%d%d", &f, &m) != EOF) { // 读取消防站数量和路口数量
        memset(book, 0, sizeof(book));    // 初始化消防站标记数组
        for(i=1; i<=m; i++)
            ans[i] = INF;                 // 初始化最近距离为无穷大

        for(i=0; i<f; i++) {
            scanf("%d", &t1);             // 读取现有消防站位置
            book[t1] = 1;                 // 标记消防站
        }

        // 初始化邻接矩阵
        for(i=1; i<=m; i++) {
            for(j=1; j<=m; j++) {
                e[i][j] = (i==j) ? 0 : INF; // 自身距离为0，其他为INF
            }
        }

        // 读取道路信息
        while(scanf("%d%d%d", &t2, &t3, &t4) != EOF) {
            e[t2][t3] = e[t3][t2] = min(t4, e[t2][t3]); // 双向道路，取最小值
        }

        Floyd(); // 计算所有路口间的最短路径

        // 计算每个路口到最近消防站的距离
        for(i=1; i<=m; i++) {
            if(book[i]) // 如果是消防站，距离为0
                ans[i] = 0;
            else
                for(j=1; j<=m; j++) {
                    if(book[j]) // 遍历所有消防站，取最小距离
                        ans[i] = min(ans[i], e[i][j]);
                }
        }

        int ansmin = INF; // 最小化最大距离
        int biaohao;      // 最优消防站位置
        for(i=1; i<=m; i++) { // 枚举每个路口作为新消防站
            int temp = -1;
            for(j=1; j<=m; j++) {
                // 计算添加新消防站后，路口j到最近消防站的距离
                temp = max(min(e[i][j], ans[j]), temp);
            }
            if(ansmin > temp) { // 更新最优解
                ansmin = temp;
                biaohao = i;
            }
        }

        printf("%d\n", biaohao); // 输出最优路口编号
    }
    return 0;
}

复杂度分析

• 时间复杂度：Floyd算法的时间复杂度为$O(m^3)$，其中$m$为路口数量。枚举新消防站位置的时间复杂度为$O(m^2)$，总时间复杂度为$O(m^3)$。
• 空间复杂度：邻接矩阵的空间复杂度为$O(m^2)$。