UVa 523

From Algorithmist

Contents 1 523 - Minimum Transport Cost 2 Summary 3 Explanation 4 Gotcha's 5 Notes 6 Input 7 Output 8 References

[edit] 523 - Minimum Transport Cost

• http://acm.uva.es/p/v5/523.html

[edit] Summary

This is a fairly typical single source Shortest Path problem.

[edit] Explanation

We are given a distance matrix D, where D_i,j represents the cost of moving from city i to city j. We are also given a tax vector T. When moving through (eg, not starting or ending) at city k, we must pay a tax of T_k. We are also given a list of source sink pairs which we must compute the shortest path between. When computing the shortest path from s to t, we can simply form a new distance matrix D' such that D'_i,j = D_i,j + T_j iff and otherwise D'_i,j = D_i,j. Then we can simply compute the Shortest Path from s to t in D' with a standard algorithm.

[edit] Gotcha's

• This is a Multiple Input problem.

[edit] Notes

• There is a special judge program, any shortest path is acceptable.
• The given output will produce a presentation error

[edit] Input

2

0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4

0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4

[edit] Output

From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17


From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17

[edit] References

Multiple Input Problems