Module assignment: city route planner

Why this assignment

This assignment puts the whole module to work on one problem. You will read a road map, then answer three kinds of question about it. One question counts roads. One asks for the cheapest trip. One asks for the cheapest set of roads that keeps every town connected. Each question needs a different tool from this module: BFS for the first, Dijkstra for the second, and union-find with Kruskal's algorithm for the third. You can finish it using only the lessons in this module. It is graded with a rubric, so you can see what each level of work looks like before you start. Read the whole page once, then work through the checklist in order. The hints are hidden under their own headings, so try the problem yourself first. The reference solution is at the end, and it is there so you can compare your answer after you have written your own.

The problem

A regional tourism office keeps a map of towns and the roads between them. Each road joins two towns, works in both directions, and has a length in kilometres. The office wants a small program that answers three questions from the map:

• hops a b: what is the fewest number of roads you must drive to get from town a to town b? Road lengths do not matter for this question, only the number of roads. The answer is -1 if no route exists.
• cheapest a b: what is the smallest total length of a route from town a to town b? The answer is -1 if no route exists.
• network: what is the smallest total length of a set of roads that connects every town? The answer is -1 if some towns cannot be reached from the others, because then no set of roads connects everything.

Each question is one line of input, and each answer is one line of output. The program reads the map once and answers every question from it.

Input format

The first line holds n and m. n is the number of towns, numbered 0 to n - 1, and m is the number of roads. You can assume 2 to 2000 towns and 0 to 20000 roads.

Each of the next m lines holds three numbers u v w. This means there is a two-way road between town u and town v with length w. The length is an integer from 0 to 1000000. Towns are never joined to themselves.

The next line holds q, the number of questions. q is from 1 to 1000.

Each of the last q lines is one question. It is either hops a b, cheapest a b, or the single word network, with no numbers after it.

Output format

Print one line for each question, in the order the questions were asked. Print a whole number. Print -1 when the answer does not exist.

Examples

Here is the first example. Type the whole block into the Input box to try it:

6 7
0 1 4
0 2 1
2 1 2
1 3 1
2 3 5
3 4 3
4 5 9
5
hops 0 4
cheapest 0 4
cheapest 0 5
network
hops 2 2

The output must be:

3
7
16
16
0

Check the first answer by hand. The fewest roads from town 0 to town 4 are 0, 1, 3, 4, which uses three roads. The cheapest route 0, 2, 1, 3, 4 has length 1 + 2 + 1 + 3 = 7. The route to town 5 adds the road of length 9 to reach town 5, so the length is 16. The cheapest network uses the roads of length 1, 1, 2, 3 and 9, which is 16. The last question asks for the hops from a town to itself, which is 0.

Here is a second example with a town that cannot be reached:

3 1
0 1 5
3
network
cheapest 0 2
hops 0 1

The output must be:

-1
-1
1

Town 2 has no roads, so no route reaches it and no network connects all three towns. The route from 0 to 1 is one road, so the answer is 1.

What you must build

Build one C++ program that reads the input, stores the map, and answers each question. Use #include lines for the headers you need, and a main function that reads with cin and writes with cout. Your program may use the standard library, but it must not read the input more than once.

You should store the map in two forms. An adjacency list of (neighbour, length) pairs is what Dijkstra needs. A plain list of neighbours is enough for the fewest-hops search, because BFS ignores lengths. You may also keep a list of the roads for Kruskal's algorithm, since it needs to sort them. Choose the forms carefully: storing the map twice is fine, but do not rebuild anything for every question if you can avoid it.

Each question is answered by its own method. Use BFS for hops, Dijkstra for cheapest, and union-find with Kruskal for network. The network answer does not depend on the source town, so compute it once and reuse it if you like, though computing it each time is acceptable within the limits.

Requirements checklist

Work through this list. Each item is something the grader checks. Tick an item only when you have tested it yourself.

• The program reads the whole input from cin and does not use files.
• The first sample input prints exactly the five lines shown.
• The second sample input prints exactly the three lines shown.
• A hops question ignores road lengths and counts roads only.
• A cheapest question uses road lengths and not the number of roads.
• A question between two different towns that have no route prints -1.
• A question from a town to itself prints 0 for hops and cheapest.
• A network question prints -1 when the map is not connected.
• A network question with a single town prints 0.
• A map with no roads (m is 0) and two or more towns prints -1 for network.
• The program handles q up to 1000 questions on a map with n up to 2000 and m up to 20000 within a few seconds.
• Distances use a type large enough for the sum. Road lengths can reach a total of several billion over a long route, so use long long.
• Unreached towns are never used to compute a distance. The guard checks that a value is not infinity before adding to it.
• The program prints a newline after every answer.

Grading rubric

Your work is graded against three levels. The levels describe what a typical solution looks like, not a list of tests you must pass in an exact order.

60 percent: the program runs and answers some questions

A 60 percent solution reads the input and prints an answer for every question. The answers for hops are correct when the map is connected, and the answers for cheapest are correct on the first sample. The solution may fail on network, or on towns that cannot be reached. It may give the wrong answer when the cheapest route has more roads than the fewest-hops route. It may print nothing for a question it does not recognise.

A 60 percent solution shows that you can read a graph, run BFS, and run Dijkstra. Those are the core tools, and you have used them in this module.

80 percent: the program is correct on small maps

An 80 percent solution gets every sample right and every small case right. It prints -1 for towns with no route. It gives 0 when the start and the goal are the same town. It computes the network total correctly on a connected map, and prints -1 when the map is not connected. It uses union-find or an equivalent check to tell whether two towns are already joined when it builds the network.

Most mistakes at this level are about edge cases. The usual ones are a missing guard on infinity, a network check that counts edges but not connections, and a hops answer that uses lengths.

100 percent: the program is correct and fast on large maps

A 100 percent solution is correct on every test, including the large ones with thousands of towns and roads. It runs within the time limit with a comfortable margin. It uses the right integer type for the sums. It uses a min-heap for Dijkstra and a sort plus union-find for Kruskal, with no step that is slower than it needs to be, such as scanning all towns to find the cheapest unvisited one on every question.

A 100 percent solution is also tidy. The distance arrays are local to each question, so nothing from one question leaks into the next. The program has one clear function for each question type, or at least one clear block of code for each. Comments explain the non-obvious steps, such as why the guard is there and why the network check counts edges.

Step-by-step hints

Try each step yourself first. If you are stuck, open the hint for that step.

Step 1: read the map

Read n and m. Create the storage for the map before you read the roads. Read each road and put it in both directions in the adjacency list. Keep the roads in a separate list as well, because Kruskal needs them as a list. Then read q, and only then start reading questions.

Step 2: answer hops with BFS

Run BFS from the start town, using the plain list and a dist vector set to -1. Set the start's distance to 0 and push it into a queue. When you pop a town, look at each neighbour. If its distance is still -1, set it to one more than the popped town's distance, and push it. When the search ends, print dist[b], which is -1 if b was never reached.

Step 3: answer cheapest with Dijkstra

Run Dijkstra from the start town, using the weighted list. Use a vector<long long> for the costs, starting at LLONG_MAX. Set the start's cost to 0 and push the pair (0, start) into a min-heap. Pop pairs in order. Skip a pair when its cost is larger than the town's current cost. Otherwise relax each road: if the cost plus the road length is smaller than the neighbour's cost, update it and push the new pair.

Print the cost of b, or -1 if it is still LLONG_MAX.

Step 4: answer network with union-find and Kruskal

Sort the roads by length, from smallest to largest. Create a union-find structure with one group per town. Go through the sorted roads. For each road, try to unite its two ends. If the union succeeds, add the road's length to a total and count the road. Stop when you have counted n - 1 roads, or let the loop finish.

After the loop, if the count equals n - 1, print the total. Otherwise print -1.

Step 5: put it together and test

Build the program and run both samples. Check each line against the expected output. Then write three or four small maps of your own, with answers you can work out by hand: a map with one town, a map with no roads, a map that is a line, and a map with a cheap long route and an expensive short route. Compare your program's answers with yours. If they differ, find which line is wrong by printing the distances after each step.

Common mistakes

Three mistakes account for most lost marks.

The first is using the lengths in the hops answer. The question asks for the number of roads, so the BFS must count roads, and a road of length 1000000 counts the same as a road of length 1. A hops answer that is too large, or that differs from a simple count, usually means lengths leaked in.

The second is treating an unreached town as reachable. If the cost of an unreached town is LLONG_MAX and the program adds a road to it, the sum overflows. Check the cost before you add, as in step 3. The same goes for dist in BFS, where a -1 value must not be used in arithmetic.

The third is a network check that counts edges without checking connection. The count n - 1 is the test. A map with n - 1 roads can still be disconnected if some roads form a loop, and union-find catches that, because a road whose ends are already together is not counted. Make sure you count only successful unions.

Stretch extension

When the core program is correct on every test, you can extend it. Add a fourth question, route a b, which prints the cheapest route itself rather than only its length. Use the parent array from the Dijkstra lesson, and print the towns in order from a to b. Print -1 when there is no route.

A second stretch is to make the network question faster for many repeated questions. Compute the network total once, after reading the map, and store it. Then each network question prints the stored value. Explain in a comment why this is correct, and why it would be wrong if the map could change between questions.

A third stretch asks you to find a road that, if removed, leaves the map disconnected. These roads are called bridges in the graph literature. Every bridge must be in every spanning tree, so you only need to test the roads of the minimum spanning tree. For each one, run union-find again over all the other roads, and check whether every town is still joined. Be careful: removing a tree road always splits the tree, but the map may still be connected through another road, so the test must use all the roads except that one. Test it on a small map before you trust it.

Reference solution

Read the solution only after you have written your own, or after you have tried all the steps and still have a problem you cannot find. Compare it with your program line by line. Differences in layout are fine. Differences in what the code computes are the bugs to look for.

#include <algorithm>
#include <climits>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>
#include <vector>
using namespace std;
 
struct DSU {
    vector<int> parent, size;
    DSU(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        return true;
    }
};
 
struct Road {
    int u, v, w;
};
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<Road> roads(m);
    vector<vector<pair<int, int>>> weighted(n);   // (neighbour, length)
    vector<vector<int>> plain(n);                 // neighbours only
    for (auto& r : roads) {
        cin >> r.u >> r.v >> r.w;
        weighted[r.u].push_back({r.v, r.w});
        weighted[r.v].push_back({r.u, r.w});
        plain[r.u].push_back(r.v);
        plain[r.v].push_back(r.u);
    }
    vector<Road> byLength = roads;
    stable_sort(byLength.begin(), byLength.end(), [](const Road& x, const Road& y) { return x.w < y.w; });
 
    int q;
    cin >> q;
    while (q-- > 0) {
        string kind;
        cin >> kind;
        if (kind == "network") {
            DSU d(n);
            long long total = 0;
            int taken = 0;
            for (auto& r : byLength) {
                if (d.unite(r.u, r.v)) {
                    total += r.w;
                    taken++;
                }
            }
            cout << (taken == n - 1 ? total : -1) << "\n";
            continue;
        }
        int a, b;
        cin >> a >> b;
        if (kind == "hops") {
            vector<int> dist(n, -1);
            queue<int> bfs;
            dist[a] = 0;
            bfs.push(a);
            while (!bfs.empty()) {
                int v = bfs.front();
                bfs.pop();
                for (int w : plain[v]) {
                    if (dist[w] == -1) {
                        dist[w] = dist[v] + 1;
                        bfs.push(w);
                    }
                }
            }
            cout << dist[b] << "\n";
        } else {
            vector<long long> dist(n, LLONG_MAX);
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
            dist[a] = 0;
            pq.push({0, a});
            while (!pq.empty()) {
                auto [d, v] = pq.top();
                pq.pop();
                if (d > dist[v]) continue;
                for (auto [w, c] : weighted[v]) {
                    if (d + c < dist[w]) {
                        dist[w] = d + c;
                        pq.push({dist[w], w});
                    }
                }
            }
            cout << (dist[b] == LLONG_MAX ? -1 : dist[b]) << "\n";
        }
    }
}

A short explanation of the solution is useful, because the grader looks at the reasoning as well as the output. The program builds two lists of the map and one sorted list of roads, which is all three answers need. Each question reads its two towns, and hops runs BFS on the plain list, which ignores lengths. The cheapest question runs Dijkstra on the weighted list, with the skip test and a min-heap. The network question sorts the roads once and then runs union-find over the sorted list, counting successful unions and printing the total only when the count is n - 1. The guard dist[b] == LLONG_MAX stops an unreached town from being printed as a huge number.

What you now know

• A road map is a graph. Store it as an adjacency list, with lengths when the question needs them.
• BFS answers fewest-roads questions and ignores lengths.
• Dijkstra with a min-heap answers cheapest-route questions when every length is zero or more.
• Kruskal with union-find builds the cheapest network, and the count of n - 1 roads tells you whether the map is connected.
• A grader checks edge cases as hard as the main path: towns with no route, a town to itself, a map with no roads, and very large sums.
• A complete answer shows the tool for each question and the reason it is correct.