/* Subject: Contest submission for problem #3, file 3.java */ /* jeffpast@imail.EECS.Berkeley.EDU */ /* Thu Nov 20 12:11:37 PST 2003 */ /*___CONTEST_SUBMISSION___ jeffpast 3 */ /* * P3.java * * Created on September 17, 2003, 5:24 PM */ import java.io.*; import java.util.*; /** * Time estimate: 1:30 * Actual time: 1:15 (including breaks) * @author Jeff */ class P3 { static Graph graph = new Graph(); /** Creates a new instance of P3 */ public P3() { } /** * We'll shoot for edges^2 time...better is possible, but, amazingly, I remain unconcerned */ public static void main(String[] args) throws IOException { StreamTokenizer t = new java.io.StreamTokenizer(new InputStreamReader(System.in)); t.nextToken(); int roomCount = (int)t.nval; //Node[] rooms = new Node[roomCount]; for (int i = 0; i < roomCount; i++) graph.AddNode(i); t.nextToken(); //read in edges while (t.ttype != t.TT_EOF && t.ttype != '=') { int r1 = (int)t.nval; t.nextToken(); int r2 = (int)t.nval; t.nextToken(); int dist = (int)t.nval; t.nextToken(); graph.AddEdge(graph.GetNode(r1),graph.GetNode(r2),dist); //rooms[r1].edges.add(new Edge(r2,dist)); //rooms[r2].edges.add(new Edge(r1,dist)); } //find a path and save the distances in the room objects LinkedList foodPath = FindPath(1, 0,graph.nodes, true); Iterator i = foodPath.iterator(); while (i.hasNext()) { Node nextNode = (Node)i.next(); if ( ((Node)FindPath(2, nextNode.id,graph.nodes,false).getLast()).itag1 * 2 < nextNode.itag3) { System.out.println("Snark eats"); System.exit(0); return; } } System.out.println("Borogove escapes"); System.exit(0); } static public LinkedList FindPath(int start, int finish, LinkedList roomList, boolean saveDistance){ Node[] rooms = (Node[])roomList.toArray(); for (int i = 0; i < rooms.length; i++) { //itag1 == distance //itag2 == prev rooms[i].itag1 = Integer.MAX_VALUE/2; rooms[i].itag2 = -1; } rooms[start].itag1 = 0; //itag3 == sdistance if (saveDistance) rooms[start].itag3 = 0; rooms[start].itag2 = start; for (int i = 0; i <= rooms.length; i++) { for (int j = 0; j < rooms.length; j++) { //iterate over the edges of each node Iterator e = rooms[j].edges.iterator(); while (e.hasNext()) { Edge nextEdge = (Edge)e.next(); if (rooms[j].itag1 + nextEdge.weight < nextEdge.node.itag1 || (rooms[j].itag1 + nextEdge.weight == nextEdge.node.itag1 && j < nextEdge.node.itag2)) { nextEdge.node.itag1 = rooms[j].itag1 + nextEdge.weight; nextEdge.node.itag2 = j; if (saveDistance) nextEdge.node.itag3 = nextEdge.node.itag1; } } } } LinkedList result = new LinkedList(); int nextRoom = finish; result.add(rooms[nextRoom]); do { nextRoom = rooms[nextRoom].itag2; result.addFirst(rooms[nextRoom]); } while (nextRoom != start); return result; } } class Graph { public LinkedList nodes = new LinkedList(); //public LinkedList edges = new LinkedList(); public Node AddNode (int id) { Node node = new Node(); node.id = id; nodes.add(node); return node; } public Node GetNode(int index){ return (Node)nodes.get(index); } public Node GetNodeFromID(int id) { for (int i = 0; i < nodes.size(); i++) { Node nextNode = GetNode(i); if (nextNode.id == id) return nextNode; } return null; } public void AddEdge(Node node1, Node node2, int weight) { node1.AddEdge(node2,weight); node2.AddEdge(node1,weight); } } class Node { public int id; public Object tag1=null; public Object tag2=null; public int itag1=0; public int itag2=0; public int itag3=0; public int itag4=0; public LinkedList edges = new LinkedList(); public Edge AddEdge (Node dest, int weight) { Edge edge = new Edge(); edge.weight = weight; edge.node = dest; this.edges.add(edge); return edge; } public LinkedList Neighbors (){ LinkedList result = new LinkedList(); ListIterator i = edges.listIterator(); while (i.hasNext()) { Edge nextEdge = (Edge)i.next(); result.add(nextEdge.node); } return result; } } class Edge { public int weight = 1; public Node node; //public Node node2; }