UVa 627

From Algorithmist

Contents 1 627 - The Net 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Implementations 7 Optimizations 8 Input 9 Output

[edit] 627 - The Net

• http://acm.uva.es/p/v6/627.html

[edit] Summary

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

[edit] Explanation

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

[edit] Gotchas

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

[edit] Notes

• Anything special to note about the problem.

[edit] Implementations

Notes/Hints on actual implementation here.

[edit] Optimizations

Optimizations here.

[edit] 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

[edit] 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