# UVa 627

## Summary

Given a set of routers (nodes) (where ${\displaystyle 2\leq N\leq 300}$), for a set of queries, find the shortest path.

## Explanation

Since ${\displaystyle N\leq 300}$, Floyd-Warshall's Algorithm is out of the way. Still, an ${\displaystyle O(N^{2})}$ algorithm is suffice for this problem - use breadth-first search.

## Gotchas

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

## Notes

• Anything special to note about the problem.

## Implementations

Notes/Hints on actual implementation here.

## Optimizations

Optimizations here.

## Input

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

-----
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