USACO 2014 December Contest, Silver - Piggyback

 Problem Link

Tags: BFS
Time Complexity: O(N + M)

In this problem, Bessie the cow and Elsie the cow are located in field 1 and 2 respectively and want to reach field N. To do this, they must walk along a series of roads. When Bessie walks along a road, she spends B units of energy and when Elsie walks along a road, she spends E units of energy. But, if Bessie and Elsie walk together, then they spend P units of energy collectively. Find the least amount of energy Bessie and Elsie will have to spend to get to field N.

The energy spent from travelling to node a to node b is the number of roads from a to b * amount of energy spent per road.

This is a graph problem, since the fields can be represented as nodes, and the roads can be represented as edges. The edges are unweighted and bidirectional.

There are 2 ways the cows can reach node N:

1. Bessie and Elsie travel alone to node N, in which case the total energy spent is distance travelled by Bessie * B + distance travelled by Elsie * E, where the distance is the number of edges traversed.
2. Bessie and Elsie meet at a common node, and then travel together. The total energy spent will be distance travelled by Bessie to common spot * B + distance travelled by Elsie to common spot * E + distance travelled to node N from common spot * P.

In both cases, we want to minimize the energy spent, so we need to minimize number of roads traversed as much as possible. To do this, find the shortest path from the start to the destination in each of the cases described above using BFS, since the graph is unweighted. 

The answer is the minimum of the total energy spent in each of the two cases.

Code

#include <bits/stdc++.h>

using namespace std;

int B, E, P, N, M;

vector <vector <int>> adj;

int bfs(vector <int> &dis, int start, int increment){

    queue <int> q;

    q.push(start);

    vector <bool> visited(N+1);

    dis[start] = 0;

    visited[start] = true;

    while (!q.empty()){

        int a = q.front();

        q.pop();

        for (auto i : adj[a]){

            if (visited[i])

                continue;

            visited[i] = true;

            dis[i] = dis[a] + 1;

            q.push(i);

        }

    }

    return dis[N] * increment;

}

int main()

{

    freopen("piggyback.in", "r", stdin);

    freopen("piggyback.out", "w", stdout);

    cin >> B >> E >> P >> N >> M;

    adj.resize(N+1);

    for (int i = 0; i < M; i++){

        int a, b;

        cin >> a >> b;

        adj[a].push_back(b);

        adj[b].push_back(a);

    }

    int ans = 0;

    vector <int> bessie_dis(N+1), elsie_dis(N+1), combined_dis(N+1);

    ans += bfs(bessie_dis, 1, B);

    ans += bfs(elsie_dis, 2, E);

    bfs(combined_dis, N, 0);

    int node, closest_node_dis = INT_MAX;

    for (int i = 1; i <= N; i++){

        if ((bessie_dis[i] * B + elsie_dis[i] * E) + combined_dis[i] * P < closest_node_dis){

            closest_node_dis = (bessie_dis[i] * B + elsie_dis[i] * E) + combined_dis[i] * P;

            node = i;

        }

    }

    ans = min(ans, closest_node_dis);

    cout << ans << '\n';

}