Generation

generate functionThu, 20 Jul 2023

# A weighted directed graph can be represented with g_nodes nodes numbered from 1 to g_nodes and g edges edges. The th edge connects the nodes numbered g from[i] to g_to[i] and has a weight g weight[i]. In an operation, a particular edge can be selected and made bi-directional and its weight is set to 0. The cost of travel from node x to node y is defined as the minimum sum of weights of the edges in any path from node x to node y Given g nodes, g_edges, g from, g to, and two integers, source, and target, report an array of g edges integers where the ith integer represents the cost of travel from the node numbered source to the node numbered target by performing the given operation on the ith edge i.e. the edge connecting g_from[i] and g to[i] with weight g_weight[i]. If there is no path from source to target after performing the operation on some edge, report -1 as the answer for the particular edge. Example Suppose the g_nodes = 5, g edges = 7, g_from= [1, 1, 2, 2, 3, 3, 4], g to = [2, 3, 4, 5, 2, 4, 5], source = 1, and target = 5. The graph can be visualized as:After performing the operation on the edge from 1 to 2, the optimal path will be 1 to 2 to 4 to 5 with a cost of 0 + 5 + 2 = 7 2After performing the operation on the edge from 1 to 3, the optimal path will be 1 to 3 to 4 to 5 with a cost of 0 + 13 + 2 = 15 . 3After performing the operation on the edge from 2 to 4, the optimal path will be 1 to 2 to 4 to 5 with a cost of 17 + 0 + 2 = 19 4. After performing the operation on the edge from 2 to 5, the optimal path will be 1 to 2 to 5 with a cost of 17+0=17. 5After performing the operation on the edge from 3 to 2, the optimal path will be 1 to 3 to 2 to 4 to 5 with a cost of 6 + 0 + 5 + 2 = 13 6. After performing the operation on the edge from 3 to 4, the optimal path will be 1 to 3 to 4 to 5 with a cost of 6 + 0 + 2 = 8 7. After performing the operation on the edge from 4 to 5, the optimal path will be 1 to 3 to 4 to 5 with a cost of 6 + 13 + 0 = 19 . Hence the answer is [7, 15, 19, 17, 13, 8, 19]. Function Description Complete the function getTravelCosts in the editor below. getTravelCosts takes the following arguments: int source: The start node int target: The destination node int g_nodes: The number of nodes in the graph int[g edges] g_from: One end of the edges in the graph int[g edges] g_to: The other end of the edges in the graph intig edgesg weight: The weights of the edges in the graphintig edges]: The cost of travel from source to target by performing the operation on the respective edges

``````vector<int> getTravelCosts(int source, int target, int g_nodes, vector<int> g_from, vector<int> g_to, vector<int> g_weight) {
vector<int> result;
vector<vector<pair<int,int>>> graph(g_nodes);
for(int i = 0; i < g_edges; i++)
{
graph[g_from[i]].push_back(make_pair(g_to[i], g_weight[i]));
graph[g_to[i]].push_back(make_pair(g_from[i], g_weight[i]));
}
vector<bool> visited(g_nodes);
priority_queue<pair<int,int>> pq;
pq.push(make_pair(0, source));
while(!pq.empty())
{
pair<int,int> current = pq.top();
pq.pop();
if(!visited[current``````