代写159.201、代写C/C++编程设计

日期：2023-05-18 09:20

159.201 Algorithms & Data Structures

Assignment 6

Write a C++ program that reads a simple (no loops or parallel edges) edge-weighted directed

graph G = (V, E) from standard input, and computes the distance from node zero to all other

nodes. Your code must run in O(n · log n) with n = |V | + |E|. This can be achieved by using

adjacency lists to represent the graph, and by computing distances using Dijkstra’s algorithm

with a heap to identify the next node (with minimum distance) to process.

Input graphs are given in the format

n m

v1 w1 l1

v2 w2 l2

.

.

.

vm wm lm

Here n ≥ 1 and m ≥ 0 denote the number of nodes and edges in the graph, and each of the

following line describes an edge from vi to wi of length li

. All nodes vi

, wi

lie in [0 . . . n), and

li

is a positive integer between 1 and 99. There can be nodes that are unreachable from node

zero. For all other nodes, it is guaranteed that the distance from zero will not exceed 106

.

Your program should print the distances from node zero to all other nodes in ascending order,

separated by a single space. When a node is unreachable, print inf instead. For example:

0 1 2

3 4 5

4

2

99

2

1 3 1 3

Input Output

6 8 0 3 8 2 inf 5

0 1 4

0 3 2

1 2 99

1 5 2

2 5 1

3 1 1

4 1 3

5 2 3

You can use CodeRunner to test your work, but must submit your assignment as usual. If

teamwork is permitted and you work in a team, you must include the names and student IDs

of all team members as comments in your submission, and each team member must submit the

same assignment separately.