UVa 558

From Algorithmist

Contents 1 558 - Wormholes 2 Summary 3 Explanation 4 Gotcha's 5 Implementation 6 Input 7 Output

[edit] 558 - Wormholes

• http://acm.uva.es/p/v5/558.html

[edit] Summary

Given a weighted directed graph, find whether a negative weight cycle exists in it or not.

[edit] Explanation

This one is related to graph theory. The trick is to realize that the problem is talking about a graph data structure. Each star system is a node and each wormhole is an edge (with time t as the weight). After building the adjacency list (or matrix) to represent the graph in memory, you need to find whether it contains any negative weight cycles or not. This can be easily done through a standard algorithm called Bellman-Ford.

[edit] Gotcha's

The judge program for this problem expects a newline after the last output and gives a Presentation Error if a new line is not printed after the last output.

[edit] Implementation

Watch out for stack overflow errors. Don't use arrays, use a vector instead.

[edit] Input

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

[edit] Output

possible
not possible