# UVa 523

## Summary

This is a fairly typical single source Shortest Path problem.

## Explanation

We are given a distance matrix D, where ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle D'_{i,j}=D_{i,j}+T_{j}}$ iff ${\displaystyle j\not =s}$ and ${\displaystyle j\not =t}$ otherwise ${\displaystyle D'_{i,j}=D_{i,j}}$. Then we can simply compute the Shortest Path from s to t in D' with a standard algorithm.

## Notes

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

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

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