If I'm reading your question correctly, your problem has a two interesting properties:
- The graph is connected sequentially, A->B->C->D. There may be multiple edges between nodes, but there are never edges that "skip" nodes (A->C, B->D) or loop back (C->A).
- The ultimate goal is feasibility versus optimality. That is, you want to know if a traveler has enough money versus which path costs the absolute least.
Is that correct? If so, there are a few tricks available.
First, calculate the expected value in both gold and bronze between each city. The expected value would be the minimum you would expect to pay. Given AB1 = 5 gold, AB2 = 5 bronze, and AB3 = 10 gold or bronze (I'm adding the road to illustrate a point), you would never select AB3. AB1 or AB2 give you a better solution regardless of the coin you use. Therefore, the expected value between A and B is 5 gold and 5 bronze. The expected value between B and C is 8 gold and 10 bronze. Again, we would never select BC1 (10 gold or bronze) when spending gold as BC2 (8 gold) is always cheaper. Continue calculating the expected values for the rest of your path.
Next, total your expected values for each coin. You're basically acting as if you paid all tolls using one coin type, but you're doing it for both types in one pass. If your expected values are:
- A->B 5 gold, 5 bronze
- B->C 8 gold, 10 bronze
- C->D 10 gold, 7 bronze
Your totals are 23 gold and 22 bronze. If you started with 23 or more gold and 22 or more bronze, you're done. You know that a feasible solution exists. More likely, your expected totals will be greater than your coins available.
In that case, make a choice between expected value pairs versus considering both options. If you're short on gold, spend bronze where it returns the most gold. For example, if I start with 13 gold, I can select the bronze payment option between C->D to create a feasible solution. If I start with 5 bronze, I can select the gold payment option between B->C and C->D to create a feasible solution.
Again, that's probably wishful thinking. It's likely you'll be short both gold and bronze. If that's the case, start with a heuristic to resolve expected values: if you have a larger gold deficit, select expected values that yield the greatest savings in gold before resolving bronze, try to make up the deficit with the fewest "choices" possible, etc... In the end, you may still have to try every combination of expected values to prove a feasible solution does or does not exist.
Note that this doesn't account for tolls that involve both currencies. A toll of 2 gold and 5 bronze ruins my expected value trick.