Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

using namespace std;

struct Flight {
    int from;
    int to;
    int price;
};

constexpr long long INF = numeric_limits<long long>::max() / 4;

long long cheapest_bellman_ford(int n, const vector<Flight>& flights, int src, int dst, int k) {
    vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; ++round) {
        vector<long long> next = dist;
        for (const Flight& f : flights) {
            if (dist[f.from] == INF) continue;
            long long candidate = dist[f.from] + f.price;
            if (candidate < next[f.to]) next[f.to] = candidate;
        }
        dist = move(next);
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

int main() {
    vector<Flight> chain = {{0, 1, 2}, {1, 2, 2}, {2, 3, 2}, {3, 4, 2}};
    cout << "k=2 answer=" << cheapest_bellman_ford(5, chain, 0, 4, 2) << '\n';
    cout << "k=3 answer=" << cheapest_bellman_ford(5, chain, 0, 4, 3) << '\n';
}

``

k=2 answer=8 and k=3 answer=8k=2 answer=-1 and k=3 answer=-1k=2 answer=-1 and k=3 answer=8k=2 answer=6 and k=3 answer=8

2. What does this program print? ``

cpp
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

using namespace std;

struct Flight {
    int from;
    int to;
    int price;
};

constexpr long long INF = numeric_limits<long long>::max() / 4;

long long cheapest_by_levels(int n, const vector<Flight>& flights, int src, int dst, int k) {
    vector<vector<pair<int, int>>> out(n);
    for (const Flight& f : flights) out[f.from].push_back({f.to, f.price});

    vector<long long> best(n, INF);
    best[src] = 0;
    vector<int> frontier{src};

    for (int level = 0; level <= k && !frontier.empty(); ++level) {
        vector<long long> next = best;
        vector<int> changed;
        vector<bool> queued(n, false);
        for (int city : frontier) {
            for (auto [to, price] : out[city]) {
                long long candidate = best[city] + price;
                if (candidate < next[to]) {
                    next[to] = candidate;
                    if (!queued[to]) {
                        queued[to] = true;
                        changed.push_back(to);
                    }
                }
            }
        }
        best = move(next);
        frontier = move(changed);
    }
    return best[dst] == INF ? -1 : best[dst];
}

int main() {
    vector<Flight> f = {{0, 1, 10}, {1, 2, 10}, {0, 2, 50}};
    cout << "k=0 answer=" << cheapest_by_levels(3, f, 0, 2, 0) << '\n';
    cout << "k=1 answer=" << cheapest_by_levels(3, f, 0, 2, 1) << '\n';
}

``

k=0 answer=-1 and k=1 answer=20k=0 answer=50 and k=1 answer=50k=0 answer=20 and k=1 answer=20k=0 answer=50 and k=1 answer=20

3. A caller runs cheapest_bellman_ford with k = 4. How many rounds does its loop run?

4568

4. Why must each round in cheapest_bellman_ford read the previous round's prices from a copy?

Because otherwise one round can chain several flights, so a trip can use more flights than the round count allowsBecause copying makes the function faster than updating in placeBecause a copy stops any price from ever becoming negativeBecause the destination city must be read before any flight is checked

5. Leaving out the copies, how many flight checks does cheapest_bellman_ford make when there are 1000 flights and k = 3?

Type a number.

Flights with K stops