ECE 36800 Assignment #8 
 
 Original Due: 1:00 PM, Tuesday, November 19 
 Extended: 1:00 PM, Tuesday, November 26 
 
Goal 
Consider the following scenario: you want to find an optimal route for your commute to work 
while considering factors like traffic, which may change over time. We can model this as a graph 
where each edge has a list of weights, such that each element of the list reflects the weight of that 
edge after a certain number of steps. For instance, consider the path given by 0 → 1 → 2 → 0 on 
the graph below: 
The weight of the 0 → 1 edge is initially 1. After taking the first step, the weight of the 1 → 
2 edge is 5, and after the second step, the weight of the 2 → 0 edge is 9, so the total weight of the 
path is 1 + 5 + 9 = 15. 
For simplicity, we only consider graphs where the lists of weights for each edge all have the same 
length, called the period. In general, if an edge u → v shows up at position i in the path and has a 
weight list of (x1, . . . , xn), it contributes xi mod n to the weight of that path. The goal of this 
assignment is to write a program which, given a graph like the one above, and a pair of start/end 
vertices, outputs a path from start to end with minimum weight. 
 
Input/Output 
As before, your program should take as a command-line argument the name of a text file 
describing a graph, and then respond to queries on standard input. For each query, you should 
print to standard output the shortest path as a space-separated list of vertices. 
The format of the text file is as follows: 
• The first line will look like V N , where V is the number of vertices in the graph, and 
N is the period of the edge weights. 
• Following that, there will be one line per edge, in the format 
vs vt w1 . . . wN 
where vs is an integer representing the source vertex of the edge, vt is an integer 
representing the target vertex of the edge, and each of w1 through wN are integers 
representing the list of weights for that edge. 
Each query will be given by a space-separated pair of integers, representing the indices of the start 
and end vertices, respectively.  
 
© 2024, Jongwook Kim. All rights reserved. 
 
Example 
Consider the following graph.txt file: 

This represents the graph: 

A sample run of the program is shown below: 
$ ./a8 graph.txt 

where 0 3 is the query input on stdin and 0 1 2 3 is the shortest path. Explanation: the shortest 
path from 0 to 3 is 0 → 1 → 2 → 3 with a total weight of 5 + 2 + 4 = 11, since the 
other path 0 → 2 → 3 has a total weight of 3 + 15 = 18. 
There will be multiple queries for each graph, but you may assume that all queries with the same 
start vertex will be given consecutively. 
 
Grading 
Similar to the previous programming assignment, your submission must be both correct and 
efficient (and not have any memory leaks/errors, as usual) to receive full points. The graphs will 
range in size from 10 vertices to roughly 1k vertices, and each graph will have approximately 10 
queries. For each test case, your program must produce an output within the time limit to receive 
credit. You should put a comment at the start of each method describing its functionality. 
 
Submission 
Submit any source/header files with your implementation, as well as a Makefile that builds 
a target called a8, to Gradescope. DO NOT include executables in your submission. DO NOT 
put your files inside a folder. Note that to receive points, your submission must work on 
eceprog. 
4,15 

请加QQ：99515681  邮箱：99515681@qq.com   WX：codinghelp