/* Subject: Contest submission for problem #3, file 3.java */ /* kelvinso@imail.EECS.Berkeley.EDU */ /* Thu Sep 18 02:53:29 PDT 2003 */ /*___CONTEST_SUBMISSION___ kelvinso 3 */ import java.io.InputStream; import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.StreamTokenizer; import java.util.*; import java.lang.Double; class P3 { public static void main(String[] arg) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer streamTokenizer = new StreamTokenizer(in); ArrayList rooms = new ArrayList(); streamTokenizer.nextToken(); Double size = new Double(streamTokenizer.nval); for(int i = 0; i < size.intValue(); i++) { Point p = new Point(); p.index = i; rooms.add(i, p); } while (streamTokenizer.nextToken() != StreamTokenizer.TT_EOF) { Double head = new Double(streamTokenizer.nval); streamTokenizer.nextToken(); Double tail = new Double(streamTokenizer.nval); streamTokenizer.nextToken(); Double distance = new Double(streamTokenizer.nval); Point headPoint = (Point) rooms.get(head.intValue()); Point tailPoint = (Point) rooms.get(tail.intValue()); Line line = new Line(); line.distance = distance.intValue(); line.head = headPoint; line.tail = tailPoint; headPoint.lines.add(line); tailPoint.lines.add(line); } TreeSet bDijkstra = new TreeSet(); Point bPosition = (Point) rooms.get(1); bPosition.bDistance = 0; bPosition.dijkstraDistance = 0; //System.out.println("AllBPath " + bPosition.index + ": " + bPosition.bDistance ); while(0!= bPosition.index) { ListIterator l = bPosition.lines.listIterator(); while(l.hasNext()) { Line line = (Line) l.next(); if(line.head.equals(bPosition)) { Point tail = line.tail; if(tail.dijkstraDistance == -1 || tail.dijkstraDistance > bPosition.bDistance + line.distance) { bDijkstra.remove(tail); tail.dijkstraDistance = bPosition.bDistance + line.distance; tail.bDistance = tail.dijkstraDistance; bDijkstra.add(tail); } } else if(line.tail.equals(bPosition)) { Point head = line.head; if(head.dijkstraDistance == -1 || head.dijkstraDistance > bPosition.bDistance + line.distance) { bDijkstra.remove(head); head.dijkstraDistance = bPosition.bDistance + line.distance; head.bDistance = head.dijkstraDistance; bDijkstra.add(head); } } else { System.out.println("error"); } } bPosition = (Point) bDijkstra.first(); bDijkstra.remove(bPosition); //System.out.println(bPosition.index + ": " + bPosition.bDistance ) ; } Point room = (Point) rooms.get(0); while(room.index != 1) { room.bVisit = true; ListIterator lines = room.lines.listIterator(); Point newRoom; while(lines.hasNext()) { Line l = (Line)lines.next(); if(l.head.equals(room)) newRoom = l.tail; else newRoom = l.head; if (newRoom.bDistance == room.bDistance - l.distance) { room = newRoom; break; } } } for(int i = 0; i < rooms.size(); i++ ) { ((Point) rooms.get(i)).dijkstraDistance = -1; } TreeSet sDijkstra = new TreeSet(); Point sPosition = (Point) rooms.get(2); sPosition.sDistance = 0; sPosition.dijkstraDistance = 0; //System.out.println("AllSPath: "); boolean flag = true; while(sPosition != null) { //System.out.println(sPosition.index + ": " + sPosition.sDistance); if(sPosition.bVisit && sPosition.sDistance < sPosition.bDistance) { System.out.println("Snark eats"); flag = false; break; } ListIterator l = sPosition.lines.listIterator(); while(l.hasNext()) { Line line = (Line) l.next(); if(line.head.equals(sPosition)) { Point tail = line.tail; if(tail.dijkstraDistance == -1 || tail.dijkstraDistance > sPosition.sDistance + line.distance * 2) { sDijkstra.remove(tail); tail.dijkstraDistance = sPosition.sDistance + line.distance * 2; tail.sDistance = tail.dijkstraDistance; sDijkstra.add(tail); } } else if(line.tail.equals(sPosition)) { Point head = line.head; if(head.dijkstraDistance == -1 || head.dijkstraDistance > sPosition.sDistance + line.distance * 2) { sDijkstra.remove(head); head.dijkstraDistance = sPosition.sDistance + line.distance * 2; head.sDistance = head.dijkstraDistance; sDijkstra.add(head); } } else { System.out.println("error"); } } sPosition = (Point) sDijkstra.first(); sDijkstra.remove(sPosition); } if(flag) System.out.println("Borogove escapes"); } } class Point implements Comparable{ public int index; public LinkedList lines = new LinkedList(); public int sDistance = -1; public int bDistance = -1; public boolean bVisit = false; public int dijkstraDistance = -1; public Point() {} public boolean equals(Object o) { Point p = (Point) o; return p.index == index; } public int compareTo(Object o) { if(o == null) return 1; Point p = (Point) o; if(p.dijkstraDistance == dijkstraDistance) { return index - p.index; } return dijkstraDistance - p.dijkstraDistance; } } class Line { public int distance; public Point head; public Point tail; public Line() { } }