UVa 627

From Algorithmist
Jump to navigation Jump to search

627 - The Net[edit]

Summary[edit]

Given a set of routers (nodes) (where ), for a set of queries, find the shortest path.

Explanation[edit]

Since , Floyd-Warshall's Algorithm is out of the way. Still, an algorithm is suffice for this problem - use breadth-first search.

Gotchas[edit]

  • Any points one can easily overlook?
  • The correct way to understand ambiguous formulations?

Notes[edit]

  • Anything special to note about the problem.

Implementations[edit]

Notes/Hints on actual implementation here.

Optimizations[edit]

Optimizations here.

Input[edit]

6
1-2,3,4
2-1,3
3-1,2,5,6
4-1,5
5-3,4,6
6-3,5
6
1 6
1 5
2 4
2 5
3 6
2 1
10
1-2
2-
3-4
4-8
5-1
6-2
7-3,9
8-10
9-5,6,7
10-8
3
9 10
5 9
9 2

Output[edit]

-----
1 3 6
1 3 5
2 1 4
2 3 5
3 6
2 1
-----
9 7 3 4 8 10
connection impossible
9 6 2