Treasure Map

There is treasure island which has certain number of treasures. A man found a treasure map and a set of instructions which can helps to find him those treasures.

The map contains the following information,

• Location of each treasure.
• How many coins have in each treasure.
• Roads between treasures.
• The number of coins needs to be spent on each road to travel.

Assume that there is exactly one or zero roads between two treasures, and he starts with zero coins in hand The man want to collect maximum number of coins as much as he can. He can end his travel at any treasure point.

Input Format

• first line contains number of treasures (n).
• each of next n lines contains the treasure point id number and the number of coins can be collected from that point.
• next line contains number of roads between treasure points (k).
• each of next k lines contains the pair of treasure point and cost between them each corresponding to a road.

• last line give the starting treasure point.

• All the inputs in a single line are space seperated.

• treasure ids are named from 1 to n

n
<id> <coins>
<id> <coins>
...
k
<id> <id> <cost_in_coins>
<id> <id> <cost_in_coins>
...
<start_point_id>

Constraints

Output Format

An integer that indicates the maximum number of coins the man can collect throughout the travel.

<max_coins>

Sample Input 0

5
1 10
2 20
3 40
4 12
5 10
5
1 2 2
2 3 20
3 4 10
3 5 40
4 5 20
2

Sample Output 0

48

Explanation 0

Treasure id sequence that he traveled is,

    2->1->2->3->4

Steps,

20                  (at point 2)
20 - 2 + 10 => 28   (at point 1)
28 - 2 => 26        (at point 2)
26 - 20 + 40 => 46  (at point 3)
46 - 10 + 12 => 48  (at point 4)

Sample Input 1

6
1 50
2 40
3 100
4 30
5 20
6 100
5
1 2 30
1 3 10
2 3 50
3 4 10
4 5 20
3

Sample Output 1

160

Explanation 1

Treasure id sequence that he traveled is,

3 -> 4 -> 3 -> 1 -> 2

Solution

By Januda Lelwala

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<pair<int, int>>> adj;

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v, int weight) {
        adj[u - 1].push_back({v - 1, weight});
        adj[v - 1].push_back({u - 1, weight});
    }
};

// Memoization map to store results of subproblems
unordered_map<string, int> memo;

// Helper function to create a unique key for memoization
string createKey(int node, int cash, vector<bool>& collected) {
    string key = to_string(node) + ":" + to_string(cash);
    for (bool b : collected) {
        key += ":" + to_string(b);
    }
    return key;
}

int findpath(Graph& g, int node, vector<bool>& collected, int cash, vector<int>& price) {
    string key = createKey(node, cash, collected);

    // Check if we already computed this state
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }

    int maxcash = cash;

    // Collect coins at current node if not already collected
    bool wasCollected = collected[node];
    if (!wasCollected) {
        cash += price[node];
        collected[node] = true;
        maxcash = cash;
    }

    // Try all adjacent nodes
    for (auto& edge : g.adj[node]) {
        int adjnode = edge.first;
        int weight = edge.second;

        if (weight <= cash) {
            int result = findpath(g, adjnode, collected, cash - weight, price);
            maxcash = max(maxcash, result);
        }
    }

    // Backtrack the coin collection status
    if (!wasCollected) {
        collected[node] = false;
    }

    // Store result in memoization map
    memo[key] = maxcash;
    return maxcash;
}

int main() {
    int num;
    cin >> num;

    Graph g(num);
    vector<bool> collected(num, false);
    vector<int> p(num);

    // Read treasure points and their coin values
    for (int i = 0; i < num; i++) {
        int node, coin;
        cin >> node >> coin;
        p[node - 1] = coin;
    }

    // Read roads between treasure points
    int edges;
    cin >> edges;
    for (int i = 0; i < edges; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        g.addEdge(start, end, cost);
    }

    // Read starting point
    int s;
    cin >> s;

    // Clear memoization map (not strictly necessary, but good practice)
    memo.clear();

    // Find maximum coins that can be collected
    cout << findpath(g, s - 1, collected, 0, p) << endl;

    return 0;
}