Light OJ 1074 - Extended Traffic

Problem link - 1074 - Extended Traffic

In this problem we have to compute minimum earning from node 1. At first we have to do a dfs to see if destination is reachable from 1.Every node that can be reached with negative earning , all its adjacent nodes can be reached with negative earning too.

If a node if not reachable from 1 or or the earning is less than 3 then we have to print '?' else we have to print ta earning from 1. We can use bellman ford algorithm from this problem as there are negative earnings.

let us analyze some test cases:

1

5

6 7 8 9 10

6

1 2

2 3

3 4

1 5

5 4

4 5

2

4

5

here node 4 (D) can be reached with earning 3 and node 5(E) can be reached with earning 4

4
10 12 15 14
2
1 2
3 4
4
1
2
3
4

here node 3(C) and node 4(D) can't be reached from 1, but 2(B) can be reached with earning 8