11492 - Babel

[mmfrb]

Is it because of "cin" ? is there a way to submit offline to see how much time does it take? Plzz help

[phantom11]

I am getting Runtime Error. Is there a problem in the test cases ?
Here is my code:

Code: Select all

import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.PriorityQueue;
import java.util.Hashtable;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.util.AbstractCollection;
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);
		Babel_11492 solver = new Babel_11492();
		solver.solve(1, in, out);
		out.close();
	}
}

class Babel_11492 {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int m, i, a, b, x;
        String start, finish, p;
        String l1, l2;
        int s, d, upperLimit = (1<<30);
        Hashtable<String, Integer> table = new Hashtable<String, Integer>();
        List<Edge> graph[] = new List[2000];
        for(i=0;i<2000;i++) {
            graph[i] = new ArrayList<Edge>();
        }
        while (true) {
            m = in.nextInt();
            if(m == 0)
                break;
            start = in.next();
            finish = in.next();

            table.clear();
            for(i=0;i<2000;i++) {
                graph[i].clear();
            }

            x = 0;
            for(i=0;i<m;i++) {
                l1 = in.next();
                l2 = in.next();
                p = in.next();
                if(table.containsKey(l1))
                    a = table.get(l1);
                else {
                    table.put(l1, x);
                    a = x++;
                }
                if(table.containsKey(l2))
                    b = table.get(l2);
                else {
                    table.put(l2, x);
                    b = x++;
                }
                int l = p.length();
                Edge e1 = new Edge(l, p.charAt(0), b);
                Edge e2 = new Edge(l, p.charAt(0), a);
                graph[a].add(e1);
                graph[b].add(e2);
            }

            if(!table.containsKey(start)) {
                out.printLine("impossivel");
                continue;
            }
            if(!table.containsKey(finish)) {
                out.printLine("impossivel");
                continue;
            }
            s = table.get(start);
            d = table.get(finish);
            if(s == d) {
                out.printLine("impossivel");
                continue;
            }
            int key[] = new int[2000];
            Arrays.fill(key, upperLimit);
            PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
            pq.add(new Vertex(s, '!', 0));
            key[s] = 0;
            while (!pq.isEmpty()) {
                Vertex u = pq.poll();
                key[u.index] = Math.min(key[u.index], u.key);
                for(Edge e : graph[u.index]) {
                    if(u.parent != e.dest && u.key + e.length < key[e.dest] && e.firstChar != u.label) {
                        Vertex v = new Vertex(e.dest, e.firstChar, e.length + u.key);
                        v.parent = u.index;
                        pq.add(v);

                    }
                }
                //for(Vertex v : pq)
                //    DebugUtils.print(v.index, v.key, v.parent, v.label);
                //DebugUtils.print("........");
            }
            if(key[d] == upperLimit) {
                out.printLine("impossivel");
            }
            else out.printLine(key[d]);
        }
    }
    class Vertex implements Comparable<Vertex> {
        int index, key, parent;
        char label;
        public Vertex(int index, char label, int key) {
            this.index = index;
            this.label = label;
            this.key = key;
            parent = -1;
        }
        public int compareTo(Vertex x) {
            return this.key - x.key;
        }
    }
    class Edge {
        int length;
        char firstChar;
        int dest;
        public Edge(int length, char fChar, int destIndex) {
            this.length = length;
            this.firstChar = fChar;
            this.dest = destIndex;
        }
    }
}

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());
    }
    }

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();
	}
}

[brianfry713]

If there are 2000 words, each connecting 2 unique languages, then there may be up to 4000 languages total.

[raj]

I am getting Runtime Error. Is there a problem in the test cases ?

while(true) is not an actual way
as sir brainfry mentioned that if 4000 lines than what happened?
in the case of
while(true) that means user take input infinite number of times that will not happen when a computer cheque your code.
They will cheque your code with limited number of lines of input. Then after completing their chequed inputs in your code. Your program will still taking the input which
occurs NullPointerException.

so in java if you use scanner use while(scanner.hasNext())
on the other hand if you use BufferedReader use like this.
String line;
while((line = bufferedReader.readLine())!=null){}