[洛谷]P1529 [USACO2.4] 回家 Bessie Come Home

**回家 Bessie Come Home**

**题目描述**

Bessie 是一只牛，住在一个叫做 "Farm" 的地方。她的家里有很多牛棚，每个牛棚都有一些牛。现在，Bessie 想要回到她自己的牛棚，但是她不知道自己当前所在的位置。帮助 Bessie 回到她自己的牛棚。

**输入**

* $n$ 是牛棚的数量。
* 每个牛棚有一个唯一的 ID，从1 到 $n$。
* 每个牛棚都有一些牛，牛的数量不超过 $1000$。
* Bessie 的当前位置是未知的。

**输出**

* 找到 Bessie 回到她自己的牛棚所需的最短路径长度。

**思路**

这个问题可以使用 Dijkstra 算法来解决。首先，我们需要建立一个图，图中每个节点代表一个牛棚，每条边代表两个牛棚之间的距离（如果两个牛棚之间没有直接连接，则该距离为无穷大）。然后，我们使用 Dijkstra 算法找到从 Bessie 当前位置到她自己的牛棚所需的最短路径长度。

**代码**

cpp#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int N =1000 +5;
const long long INF = numeric_limits<long long>::max();

struct Node {
 int id;
 long long dis;
};

bool operator<(Node a, Node b) {
 return a.dis > b.dis;
}

int main() {
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n;
 cin >> n;

 vector<vector<int>> farm(n +1, vector<int>(n +1));
 for (int i =1; i <= n; ++i) {
 for (int j =1; j <= n; ++j) {
 if (i == j) {
 farm[i][j] =0;
 } else {
 cin >> farm[i][j];
 farm[i][j] = max(farm[i][j], INF);
 }
 }
 }

 int m;
 cin >> m;

 vector<int> pos(m +1), num(m +1);

 for (int i =1; i <= m; ++i) {
 cin >> pos[i];
 cin >> num[i];
 }

 long long ans = INF;

 for (int i =1; i <= n; ++i) {
 vector<Node> dis(n +1);
 priority_queue<Node, vector<Node>, greater<Node>> q;
 for (int j =1; j <= n; ++j) {
 dis[j].id = j;
 dis[j].dis = farm[i][j];
 if (farm[i][j] != INF) {
 q.push(dis[j]);
 }
 }

 while (!q.empty()) {
 Node u = q.top();
 q.pop();

 for (int v =1; v <= n; ++v) {
 if (u.dis + farm[v][u.id] < dis[v].dis) {
 dis[v].id = u.id;
 dis[v].dis = u.dis + farm[v][u.id];
 q.push(dis[v]);
 }
 }
 }

 for (int j =1; j <= m; ++j) {
 if (pos[j] == i && ans > dis[pos[j]].dis + num[j]) {
 ans = dis[pos[j]].dis + num[j];
 }
 }
 }

 cout << ans;

 return0;
}

**注释**

* 这个代码使用了 Dijkstra 算法来找到从 Bessie 当前位置到她自己的牛棚所需的最短路径长度。
* 首先，我们建立一个图，图中每个节点代表一个牛棚，每条边代表两个牛棚之间的距离（如果两个牛棚之间没有直接连接，则该距离为无穷大）。
* 然后，我们使用 Dijkstra 算法找到从 Bessie 当前位置到她自己的牛棚所需的最短路径长度。
* 最终，我们输出这个最短路径长度。

**时间复杂度**

* 建立图的时间复杂度为 O(n^2)。
* 使用 Dijkstra 算法的时间复杂度为 O((n + m) * log(n + m))。
* 总时间复杂度为 O(n^2 + (n + m) * log(n + m))。

**空间复杂度**

* 建立图所需的空间复杂度为 O(n^2)。
* 使用 Dijkstra 算法所需的空间复杂度为 O(n + m)。
* 总空间复杂度为 O(n^2 + n + m)。