I am getting Runtime Error for this problem.
My algo is to run bellman ford to find all vertices in negative weight cycles and then run dfs for all nodes reachable by the ones in the negative weight cycles.
I have also taken care that the vertex should be in the range [0,n-1] and it passes all test cases given in this forum. Still i get RE. Can someone please report why ? I have attached my code for reference.
Code: Select all
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.Writer;
import java.util.LinkedList;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Queue;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Lokesh Khandelwal
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
Traffic_10449 solver = new Traffic_10449();
solver.solve(1, in, out);
out.close();
}
}
class Traffic_10449 {
public void solve(int testNumber, InputReader in, OutputWriter out) {
String s;
int n, i, m, u, v, q, test = 0;
int limit = (1<<27);
s = in.nextString();
while (s != null) {
test++;
StringTokenizer a = new StringTokenizer(s);
n = Integer.parseInt(a.nextToken());
List<Edge> graph[] = new List[n];
Vertex vertex[] = new Vertex[n];
int busyness[] = new int[n];
for(i=0;i<n;i++) {
vertex[i] = new Vertex(i, limit);
graph[i] = new ArrayList<Edge>();
busyness[i] = Integer.parseInt(a.nextToken());
}
m = in.nextInt();
for(i=0;i<m;i++) {
u = in.nextInt() - 1;
v = in.nextInt() - 1;
if(u >= 0 && v >= 0 && u < n && v < n)
graph[u].add(new Edge(vertex[v], (int)Math.pow(busyness[v] - busyness[u], 3)));
}
GraphUtils.bellmanFord(graph, vertex, 0, n);
boolean isOnNegativeCycle[] = new boolean[n];
for(i=0;i<n;i++) {
for(Edge e : graph[i]) {
if(vertex[i].key + e.cost < e.dest.key) {
isOnNegativeCycle[i] = true;
isOnNegativeCycle[e.dest.index] = true;
}
}
}
boolean visited[] = new boolean[n];
for(i=0;i<n;i++) {
if(!visited[i] && isOnNegativeCycle[i]) {
dfs(i, graph, visited);
}
}
for(i=0;i<n;i++) {
if(visited[i])
isOnNegativeCycle[i] = true;
}
q = in.nextInt();
out.printLine("Set #"+test);
for(i=0;i<q;i++) {
u = in.nextInt() - 1;
if(u < 0 || u >= n || vertex[u].key == limit || isOnNegativeCycle[u] || vertex[u].key < 3) {
out.printLine("?");
}
else out.printLine(vertex[u].key);
}
s = in.nextString();
}
}
public void dfs(int index, List<Edge> graph[], boolean visited[]) {
visited[index] = true;
for(Edge e : graph[index]) {
if(!visited[e.dest.index]) {
dfs(e.dest.index, graph, visited);
}
}
}
}
class InputReader
{
BufferedReader in;
StringTokenizer tokenizer=null;
public InputReader(InputStream inputStream)
{
in=new BufferedReader(new InputStreamReader(inputStream));
}
public String next()
{
try{
while (tokenizer==null||!tokenizer.hasMoreTokens())
{
tokenizer=new StringTokenizer(in.readLine());
}
return tokenizer.nextToken();
}
catch (IOException e)
{
return null;
}
}
public int nextInt()
{
return Integer.parseInt(next());
}
public String nextString()
{
try {
return in.readLine();
}
catch (Exception e)
{
return null;
}
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
class Edge {
public Vertex dest;
public int cost;
public Edge(Vertex dest, int cost) {
this.dest = dest;
this.cost = cost;
}
}
class Vertex implements Comparable<Vertex> {
public boolean visited;
public int parent, key, index, indexInHeap;
public List<Edge> edges;
public Vertex(int index) {
this.index = index;
visited = false;
parent = -1;
key = Integer.MAX_VALUE;
edges = new ArrayList<Edge>();
indexInHeap = index;
}
public Vertex(int index, int key) {
this.index = index;
visited = false;
parent = -1;
this.key = key;
edges = new ArrayList<Edge>();
indexInHeap = index;
}
public int compareTo(Vertex o) {
return this.key - o.key;
}
}
class GraphUtils {
public static void bellmanFord(List<Edge> graph[], Vertex a[], int source, int vertexCount) {
int i, j;
a[source].key = 0;
for(i=0;i<vertexCount-1;i++) { // run loop n-1 times
for(j=0;j<vertexCount;j++) {
for(Edge e : graph[j]) { // relax all edges
if(a[j].key + e.cost < e.dest.key) {
e.dest.key = a[j].key + e.cost;
e.dest.parent = a[j].index;
}
}
}
}
/*check for negative cycle
for(i=0;i<vertexCount;i++) {
for(Edge e : graph[i]) {
if(a[i].key + e.cost < e.dest.key)
return true;
}
}
*/
}
}