UVa 523

From Algorithmist
Jump to navigation Jump to search

523 - Minimum Transport Cost[edit]

Summary[edit]

This is a fairly typical single source Shortest Path problem.

Explanation[edit]

We are given a distance matrix D, where 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 . 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 iff and otherwise . Then we can simply compute the Shortest Path from s to t in D' with a standard algorithm.

Gotcha's[edit]

Notes[edit]

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

Input[edit]

3

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

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

Output[edit]

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

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

References[edit]

Multiple Input Problems