题意分析

本题要求开发一个软件系统，用于帮助纽约市消防局快速找到距离火灾地点最近的消防站。输入城市交叉点数量、交叉点之间的通行时间邻接矩阵、火灾发生地的交叉点编号以及各个消防站所在的交叉点编号，输出每个消防站到火灾地点的最短时间和最短路径，并且按照到达时间从短到长排序。

解题思路

1. 数据读取：首先读取交叉点数量 n，然后读取 n×n 的邻接矩阵 cost，表示交叉点之间的通行时间。接着读取火灾发生地的交叉点编号 fire 和各个消防站所在的交叉点编号，并记录在 target 数组中。
2. 迪杰斯特拉算法求解最短路径：对于火灾发生地 fire，使用迪杰斯特拉算法计算从 fire 到其他所有交叉点的最短路径和最短距离。在迪杰斯特拉算法中，维护一个数组 dis 记录从 fire 到各个交叉点的最短距离，一个数组 step 记录路径上的前驱节点。通过不断选择未访问的距离最小的节点，并更新其相邻节点的距离和前驱节点，直到所有节点都被访问。
3. 输出结果：遍历所有消防站（target 数组中标记为 1 的节点），找到距离火灾地点最短的距离 minstep 和对应的消防站 t，输出起点、终点、所需时间和完整路径。路径通过 step 数组从终点回溯到起点得到。

代码实现

#include <stdio.h>
#include <string.h>
#define INF 100000000

int judge[25];
int target[25];// 标记消防局
int step[105];// 记录路径
int cost[25][25];// 记录节点与节点之间的距离
int n, dis[25];// 记录从火灾地点到点I的最短路径
int fire, num;// 火灾路口以及消防局的数量
int yes = 0;

// 输出结果函数
void output() {
    if (yes != 0) printf("\n");
    printf("Org\tDest\tTime\tPath\n");
    while (num--) {
        int minstep = INF;
        int t;
        for (int i = 1; i <= n; i++) {
            if (target[i] == 1 && minstep > dis[i]) {
                minstep = dis[i];
                t = i;
            }
        }
        target[t] = 0;
        printf("%d\t%d\t%d", t, fire, dis[t]);
        while (1) {
            printf("\t%d", t);
            t = step[t];
            if (t == -1) break;
        }
        printf("\n");
    }
    yes = 1;
}

// 迪杰斯特拉算法函数
void solution(int point) {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    for (int i = 0; i < 25; i++) {
        judge[i] = 0;
    }
    for (int i = 0; i < 105; i++) {
        step[i] = -1;
    }
    dis[point] = 0;
    int x;
    while (1) {
        x = -1;
        for (int i = 1; i <= n; i++) {
            if (judge[i] == 0 && (x == -1 || dis[i] < dis[x])) x = i;
        }
        if (x == -1) break;
        judge[x] = 1;
        for (int i = 1; i <= n; i++) {
            if (judge[i] == 0 && dis[i] > dis[x] + cost[x][i]) {
                step[i] = x;
                dis[i] = dis[x] + cost[x][i];
            }
        }
    }
    output();
}

int main() {
    int t;
    char ch, x[10000];
    scanf("%d", &n);
    for (int i = 0; i < 25; i++) {
        for (int j = 0; j < 25; j++) {
            cost[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &cost[j][i]);
            if (cost[j][i] == -1) {
                cost[j][i] = INF;
            }
        }
    }
    scanf("%d", &fire);
    getchar();
    fgets(x, sizeof(x), stdin);
    int len = strlen(x);
    if (x[len - 1] == '\n') {
        x[len - 1] = '\0';
    }
    num = 0;
    for (int i = 0; i < 25; i++) {
        target[i] = 0;
    }
    for (int i = 0; i < len; i++) {
        if ('0' <= x[i] && x[i] <= '9') {
            num++;
            target[x[i] - '0'] = 1;
        }
    }
    solution(fire);
    return 0;
}

🧠 题解（Solution）

🔧 本题实质：

是一个标准的有向图最短路径问题，需要从多个起点（消防站）出发，到同一个终点（火灾发生地）计算最短路径。

✅ 解题思路

读入邻接矩阵，构建图；

将所有 $-1$ 值转为无穷大（表示无法直接到达）；

对于每个消防站：

使用 Dijkstra 算法从该消防站所在交叉点出发；

求其到火灾交叉点的最短时间；

记录并重建路径；

按时间升序输出所有消防站信息。

🧮 核心算法：Dijkstra 最短路径 适用于正权图；

维护距离数组 dist[] 和前驱数组 prev[]；

使用优先队列或手动选择当前最小未处理节点。

🧱 数据结构建议

邻接矩阵图结构（因 $N < 20$）；

路径回溯使用前驱数组 prev[]；

输出时按结果时间排序。

代码实现：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 10000000
int n,num,fire;
int edge[50][50];
int sign[50],near[50];
int loc[50];
struct node
{
    int t,p,gg;
} ans[50];
int cmp(node a,node b)
{
    return a.t<b.t;
}
void Init()
{
    cin>>n;
    int i,j;
    for(i=1; i<=n; i++)
    {
        ans[i].t=INF;
        ans[i].gg=0;
        sign[i]=0;
    }
    for(j=1; j<=n; j++)
        for(i=1; i<=n; i++)
            scanf("%d",&edge[i][j]);
    scanf("%d",&fire);
}
void Dijkstra(int v)
{
    int i,j;
    ans[v].t=0;
    for(i=0; i<n; i++)
    {
        sign[v]=1;
        int Min=INF,flag;
        for(j=1; j<=n; j++)
        {
            if(edge[v][j]>=0&&ans[v].t+edge[v][j]<ans[j].t)
            {
                ans[j].t=ans[v].t+edge[v][j];
                near[j]=v;
            }
            if(sign[j]==0&&ans[j].t<Min)
            {
                Min=ans[j].t;
                flag=j;
            }
        }
        v=flag;
    }
}
int main()
{
    int i,j;
    Init();
    Dijkstra(fire);
    int pp;
    while(scanf("%d",&pp)!=EOF)
    {
        ans[pp].gg=1;
    }
    for(i=1; i<=n; i++)
        ans[i].p=i;
    sort(ans,ans+n+1,cmp);
    cout<<"Org\tDest\tTime\tPath"<<endl;
    for(i=1; i<=n; i++)
    {
        if(ans[i].gg==1)
        {
            printf("%d\t%d\t%d\t",ans[i].p,fire,ans[i].t);
            int flag=ans[i].p;
            while(flag!=fire)
            {
                cout<<flag<<"\t";
                flag=near[flag];
            }
            cout<<fire<<endl;
        }
    }
    return 0;
}