题意分析

题目描述了贝茜在有N个地标、T条双向牛径的田野中，要从地标N（苹果树林）回到地标1（谷仓），且对每条牛径，贝茜只能从起点走到终点。已知每条牛径连接的两个地标以及牛径长度，要求找出贝茜从地标N到地标1的最短距离。

解题思路

1.采用Bellman-ford算法来求解最短路径问题。

2.初始化距离数组d，将除地标1（谷仓）外的所有地标到谷仓的距离设为无穷大（这里用1<<29表示），地标1到自身的距离设为0。

3.进行n−1次迭代（n为地标数量），每次迭代遍历所有的牛径（边）。对于每条牛径(a,b,w)，检查从b到a的距离d[a]是否可以通过d[b]+w来更新（即是否存在更短路径），如果可以则更新d[a]；同样检查从a到b的距离d[b]是否可以通过d[a]+w来更新，若可以则更新d[b]]。

4.经过n−1次迭代后，d[n]即为地标N到地标1的最短距离，输出该距离。

分析

1.Bellman-ford算法适用于求解带权有向图（本题是无向图，可看作双向有向图）的单源最短路径问题，且能处理边权为负的情况（本题边权为正）。

2.时间复杂度为O(nm)，其中n是地标数量，m是牛径数量。在本题中，n最大为1000，m最大为2000，O(nm)的时间复杂度是可以接受的。

3.空间复杂度主要由存储边的数组edge和距离数组d决定，为O(m+n)。

实现步骤

1.定义边的结构体edge，包含边的两个端点a、b和边的权值w。读取输入的牛径数量m和地标数量n。

2.依次读取每条牛径的信息（两个端点和长度），存储到edge数组中。

3.调用bellman_ford函数：

4.初始化距离数组d。

5.进行n - 1次迭代，每次迭代遍历所有边，更新距离数组d。

6.输出d[n]，即地标N到地标1的最短距离。

代码实现

#include <iostream>
using namespace std;

const int INFTY = 1 << 29;
const int MAXM = 2005;
const int MAXV = 1005;

typedef struct {
    int a, b, w;
} Edge;

Edge edge[MAXM];
int n, m;

void bellman_ford() {
    int d[MAXV];
    for (int i = 2; i <= n; i++) d[i] = INFTY;
    d[1] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (d[edge[j].a] > edge[j].w + d[edge[j].b]) 
                d[edge[j].a] = edge[j].w + d[edge[j].b];
            if (d[edge[j].b] > edge[j].w + d[edge[j].a]) 
                d[edge[j].b] = edge[j].w + d[edge[j].a];
        }
    }
    cout << d[n] << endl;
}

int main() {
    int a, b, c;
    while (cin >> m >> n) {
        for (int i = 1; i <= m; i++) {
            cin >> a >> b >> c;
            edge[i].a = a;
            edge[i].b = b;
            edge[i].w = c;
        }
        bellman_ford();
    }
    return 0;
}

代码说明

这段C++代码聚焦于解决在具有特定结构的图中求最短路径问题。 它首先引入标准输入输出流库，通过using namespace std;简化代码书写，并定义了表示无穷大的INFTY以及用于限定边数和顶点数的MAXM与MAXV常量。 接着，创建Edge结构体存储边的两个端点及权重信息，声明edge数组存放所有边。在bellman_ford函数中，定义d数组记录各顶点到起点的距离，初始化除起点外其他顶点距离为无穷大，起点到自身距离为0。之后，通过两层循环，外层循环迭代n次，内层循环遍历所有边，不断检查并更新各顶点到起点的最短距离，最终输出地标N到地标1的最短距离。 在main函数里，持续读取输入的边数m和顶点数n，将每条边的信息存入edge数组，再调用bellman_ford函数求解并输出结果 。