UVa 558

From Algorithmist
Jump to: navigation, search

558 - Wormholes[edit]

Summary[edit]

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

Explanation[edit]

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.

Gotcha's[edit]

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.

Implementation[edit]

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

Input[edit]

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

Output[edit]

possible
not possible

Solutions[edit]