From the 1997 UF ACM High School Programming Competition

All Roads Lead...

To Gainesville? No, but you're here anyways. Getting to town wasn't too difficult, but finding an efficient path from the gas station to the Union probably was. If you had a laptop and were awake enough at that ghastly hour, you probably could have helped your poor coach...

Problem Statement

Write a program to find the least expensive path between two points on the map given in figure below plus some modifications garnered from locals.

The given map consists of many directional edges, but all the edges in opposite directions between the same nodes have the same cost. This could change, and all new edges will be one-way.

Basic roadmap with costs in bold

Notes

The first phase of input will consist of a sequence of change and delete commands. A change command will change an existing arc's weight or add a new arc with the given costs between two nodes. Neither new nodes nor negative costs will be given. A delete command removes a directed edge between two nodes. Only edges which already exist will be deleted.

The exact syntax you type need not match ours, but it must not provide more information than the type of operation, the two nodes, and the cost when appropriate.

The second phase of input will ask for two nodes and output the least expensive path from the first to the second along with its cost. You may assume the destination will always be reachable.

This map is completely imaginary, although many of Gainesville's roads do lie on a grid.

Examples

Example 1:
(C)hange, (D)elete, (E)nd: c Enter origin, endpoint, and cost: 4, 5, 1
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 2, 3
(C)hange, (D)elete, (E)nd: e

Find a path from where to where? 1, 9
The shortest path from 1 to 9 has length 8 and follows 1 -> 4 -> 5 -> 6 -> 9.
Find a path from where to where? 3, 8
The shortest path from 3 to 8 has length 12 and follows 3 -> 6 -> 5 -> 8.

Example 2:
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 1, 2
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 2, 3
(C)hange, (D)elete, (E)nd: e

Find a path from where to where? 1, 3
The shortest path from 1 to 3 has length 18 and follows 1 -> 4 -> 5 -> 6 -> 3.
Find a path from where to where? 3, 1
The shortest path from 3 to 1 has length 9 and follows 3 -> 2 -> 1.

Grader's Test Data

Example 3:
(C)hange, (D)elete, (E)nd: c
Enter origin, endpoint, and cost: 1, 5, 6
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 1, 4
(C)hange, (D)elete, (E)nd: c
Enter origin, endpoint, and cost: 1, 4, 5
(C)hange, (D)elete, (E)nd: e

Find a path from where to where? 1, 4
The shortest path from 1 to 4 has length 5 and follows 1 -> 4.
Find a path from where to where? 1, 5
The shortest path from 1 to 5 has length 6 and follows 1 -> 5.
Find a path from where to where? 4, 1
The shortest path from 4 to 1 has length 2 and follows 4 -> 1.

Example 4:
(C)hange, (D)elete, (E)nd: c
Enter origin, endpoint, and cost: 1, 8, 4
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 8, 7
(C)hange, (D)elete, (E)nd: c
Enter origin, endpoint, and cost: 8, 6, 1
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 3, 2
(C)hange, (D)elete, (E)nd: d
Enter origin and endpoint: 1, 2
(C)hange, (D)elete, (E)nd: e

Find a path from where to where? 1, 9
The shortest path from 1 to 9 has length 7 and follows 1 -> 8 -> 6 -> 9.
Find a path from where to where? 1, 2
The shortest path from 1 to 2 has length 15 and follows 1 -> 8 -> 5 -> 2.
Find a path from where to where? 6, 7
The shortest path from 6 to 7 has length 12 and follows 6 -> 5 -> 4 -> 7.

Solutions

C solution by Jason Riedy:: path.c