159.201
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.
WX：codehelp
标签：node,zero,159.201,算法,team,nodes,结构,your,must From： https://www.cnblogs.com/messagejava/p/17414810.html