在信息学奥赛中，我们经常会遇到一些需要智慧和逻辑思维才能解决的问题。今天，我们将一起探讨一道名为“救援”的题目。这道题目不仅考验了我们对算法的理解，还要求我们运用C++语言进行编程实现。

🔍题目背景：

在一个偏远山区，一场突如其来的山洪暴发，导致多个村庄被洪水围困。救援队需要尽快将被困村民转移到安全地带。然而，由于地形复杂，每条道路的通行时间各不相同。如何规划一条最短路径，以最快的速度完成救援任务？

💻问题描述：

给定一个由N个村庄组成的地图（编号从1到N），以及M条连接这些村庄的道路。每条道路都有一个特定的通行时间。请编写一个程序，找出从救援基地出发，到达所有村庄并返回基地所需的最短时间。

🛠️解决方案：

为了高效地解决问题，我们可以采用Dijkstra算法来寻找最短路径。通过构建一个优先队列，我们可以逐步探索从救援基地到各个村庄的最短路径，并记录下所需的时间。最终，计算出总耗时，并输出结果。

🎯代码实现：

```cpp

include

include

include

using namespace std;

int main() {

// 初始化变量

int N, M;

cin >> N >> M;

vector>> graph(N + 1);

for (int i = 0; i < M; ++i) {

int u, v, w;

cin >> u >> v >> w;

graph[u].push_back({v, w});

graph[v].push_back({u, w});

}

// Dijkstra算法实现

vector dist(N + 1, INT_MAX);

priority_queue, vector>, greater<>> pq;

dist[1] = 0;

pq.push({0, 1});

while (!pq.empty()) {

auto [d, u] = pq.top();

pq.pop();

if (d > dist[u]) continue;

for (auto [v, w] : graph[u]) {

if (dist[u] + w < dist[v]) {

dist[v] = dist[u] + w;

pq.push({dist[v], v});

}

}

}

// 输出结果

cout << "Total time required for rescue mission: " << dist[N] 2 << endl;

return 0;

}

```

通过以上方法，我们能够有效地解决这个问题，并为救援行动提供宝贵的时间支持。希望这篇分享对你有所帮助！