极客笔记C++ 通过修改边的成本，使用Dijkstra算法找到最小成本
在这个问题中，我们需要使用Dijkstra算法找到从1到N的最小路径，并且我们可以将任意单个边的成本更新为成本/2。
在这里，我们将找到每个节点从源节点到目标节点的距离。然后，我们将取源节点到节点u的最短距离和目标节点到节点v的最短距离，并将它们与边u -> v的成本/2相加。通过这种方式，我们将找到从1到N的最小成本路径。
问题陈述 - 我们以元组的形式给出了一个无向图。元组{p，q，r}表示p和q之间的边以成本r连接。我们需要使用Dijkstra算法找到从1到N的最小成本路径。还给出我们只能执行一次操作，以使我们可以将任意边的成本更新为成本/2。
示例
输入
[{1, {2, 7}}, {1, {3, 4}}, {1, {4, 8}}, {3, {4, 4}}, {4, {5, 3}}]
输出
7
解释 - 这是给定的图表。
1
/ | \
2 3 - 4 - 5
在这里，我们需要从1到5。因此，存在两条路径。一个是 1 → 3 → 4 → 5，另一个是 1 → 4 → 5。这两条路径的成本都是11。如果我们选择第二条路径，并将 1 → 4 的成本从 8 减少到 4，路径的成本就是7。
输入
[{1, {2, 3}}, {2, {1, 6}}, {2, {3, 2}}]
输出
3
解释 - 我们在节点1和2之间给出了两条边。所以，我们可以考虑成本为3的边，并将其值更新为3/2等于1。所以，从1到3的路径的成本只有3。
方法
在这个方法中，我们将使用Dijkstra算法来查找每个节点与源节点和目标节点之间的距离。然后，对于连接两个顶点的每条边，我们将获得从源节点到起始节点的距离和从目标节点到终点节点的距离，并将它们与成本/2相加。同时，我们将跟踪1到N路径的最小成本。
步骤
步骤1 - 定义用于存储图形的列表。
步骤2 - 遍历每个给定的边，并按照以下步骤进行操作。
步骤2.1 - 从当前元组中获取源节点、目标节点和成本。
步骤2.2 - 在列表的源索引处插入{目标，成本}对，在列表的目标索引处插入{源，成本}对。
步骤3 - 此外，定义source_dist和dest_dist列表分别存储每个节点与源节点和目标节点之间的距离。
步骤4 - 两次调用executeDijkstra()函数分别找到每个节点与起始节点和终点节点之间的距离。
步骤4.1 - 在executeDijkstra()函数中，根据节点总数调整’dist’列表的大小，并将dist[source]更新为0。
步骤4.2 - 定义优先级队列并使用greater>比较函数使用最小堆与优先级队列。优先级队列将被用于存储当前节点与源节点和节点值的距离。
步骤4.3 - 将源节点插入队列中。
步骤4.4 - 遍历队列直到队列为空。在循环中，获取队列的第一个元素并遍历其边。
步骤4.5 - 在遍历边时，获取结束节点和边的成本。
步骤4.6 - 如果到起始节点的距离+边的成本小于到结束节点的距离，则更新结束节点的距离。还要将更新的对插入队列中。
步骤5 - 定义’minCost’变量并将其初始化为1到N的距离。
步骤6 - 开始遍历所有边。将起始节点与源节点的距离、成本/2以及结束节点与目标节点的距离相加。如果结果值大于minCost，则更新minCost。
步骤7 - 返回minCost的值。
示例
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
void executeDijkstra(int source, int nodes, vector<pair<int, int>> list[], vector<int> &dist) {
// Resizing
dist.resize(nodes, INF);
// Initialize source node with 0.
dist[source] = 0;
// To store edges cost
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p_que;
// Insert distance and source node
p_que.push({dist[source], source});
while (!p_que.empty()) {
// Get the first node from the queue
int start = p_que.top().second;
// Pop the top node
p_que.pop();
// Traverse all connected nodes to the current node
for (auto &ed : list[start]) {
// Get the start and end node of the edge
int end = ed.first;
int cost = ed.second;
// Updating the distance to minimum
if (dist[start] + cost < dist[end]) {
dist[end] = dist[start] + cost;
p_que.push({dist[end], end});
}
}
}
}
void getMinimumCost(vector<pair<int, pair<int, int>>> &edges, int nodes, int totalEdges) {
vector<pair<int, int>> list[100005];
// Traverse edges
for (int p = 0; p < totalEdges; p++) {
// Add graph parameters to list
int source = edges[p].first;
int destination = edges[p].second.first;
int cost = edges[p].second.second;
list[source].push_back({destination, cost});
list[destination].push_back({source, cost});
}
// To store the distance of 1 to P and N to P
vector<int> source_dist;
vector<int> dest_dist;
// For each vertex, find the path cost from the source node
executeDijkstra(1, nodes + 1, list, source_dist);
// For each vertex, find the path cost from the destination node
executeDijkstra(nodes, nodes + 1, list, dest_dist);
// To store minimum path cost
int minCost = source_dist[nodes];
for (auto &ed : edges) {
// Get the edges
int source = ed.first;
int destination = ed.second.first;
int cost = ed.second.second;
// Cost for 1 to N = (1 to P) + (p to p + 1) + (P + 1 to N)
int cur_cost = source_dist[source] + cost / 2 + dest_dist[destination];
minCost = min(minCost, cur_cost);
}
cout << "The minimum cost for 1 to N after modifying any single edge is " << minCost << '\n';
}
int main() {
int nodes = 5;
int totalEdges = 5;
vector<pair<int, pair<int, int>>> edges;
edges.push_back({1, {2, 7}});
edges.push_back({1, {3, 4}});
edges.push_back({1, {4, 8}});
edges.push_back({3, {4, 4}});
edges.push_back({4, {5, 3}});
getMinimumCost(edges, nodes, totalEdges);
return 0;
}
输出
The minimum cost for 1 to N after modifying any single edge is 7
时间复杂度 – O(MlogN)
空间复杂度 – O(N)
在这里，我们仅将1条边的成本替换为成本/2。然而，程序员可以尝试编写代码来替换K条边的成本以进行更多的练习。