nucLeaRsc2

Untitled

Jan 18th, 2015
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.58 KB | None | 0 0
  1. import java.io.BufferedWriter;
  2. import java.io.File;
  3. import java.io.FileNotFoundException;
  4. import java.io.FileWriter;
  5. import java.io.IOException;
  6. import java.io.PrintWriter;
  7. import java.util.ArrayList;
  8. import java.util.PriorityQueue;
  9. import java.util.Scanner;
  10. import java.util.Comparator;
  11.  
  12. class Road{
  13. City destination;
  14. int capacity;
  15. int time;
  16.  
  17. public Road(City destination, int cost, int time){
  18. this.destination = destination;
  19. this.capacity = cost;
  20. this.time = time;
  21. }
  22.  
  23. public String toString(){
  24. return this.destination + ": " + "Capacity: " + this.capacity + "- Time: " + this.time;
  25. }
  26. }
  27.  
  28. class City{
  29. PriorityQueue<Road> roads = new PriorityQueue<Road>(10, new Comparator<Road>(){
  30. public int compare(Road r1, Road r2) {
  31. return r1.capacity - r2.capacity == 0 ? r1.time - r2.time : r1.capacity - r2.capacity;
  32. }
  33. });
  34.  
  35. public City(int city){
  36. this.city = city;
  37. }
  38.  
  39. public String toString(){
  40. return this.city + "";
  41. }
  42.  
  43. int city;
  44. int capacityToStart = 1<<31-1;
  45. int timeToStart = 1<<31-1;
  46. boolean visited = false;
  47. City parent;
  48. }
  49.  
  50. class Trip{
  51.  
  52. int numberOfCities, numberOfRoads;
  53. int start, destination;
  54.  
  55. PriorityQueue<City> queue;
  56. ArrayList<City> cities;
  57.  
  58. public void readData(String fileName){
  59. Scanner in;
  60. try {
  61. in = new Scanner(new File(fileName));
  62.  
  63. numberOfCities = in.nextInt();
  64. cities = new ArrayList<City>(numberOfCities);
  65.  
  66. for(int i=0; i<numberOfCities; i++)
  67. cities.add(new City(i));
  68.  
  69.  
  70. Comparator<City> c = new Comparator<City>(){
  71.  
  72. @Override
  73. public int compare(City city1, City city2) {
  74. return city1.capacityToStart - city2.capacityToStart == 0 ? city1.timeToStart - city2.timeToStart : city1.capacityToStart - city2.capacityToStart;
  75. }
  76.  
  77. };
  78.  
  79. queue = new PriorityQueue<City>(10, c);
  80.  
  81. numberOfRoads = in.nextInt();
  82. start = in.nextInt();
  83. destination = in.nextInt();
  84.  
  85. while(in.hasNext()){
  86. City city1 = cities.get(in.nextInt());
  87. City city2 = cities.get(in.nextInt());
  88. int distance = in.nextInt();
  89. int time = in.nextInt();
  90.  
  91. //Road r1 = new Road(city1, distance, time);
  92. Road r2 = new Road(city2, distance, time);
  93.  
  94. city1.roads.add(r2);
  95. //city2.roads.add(r1);
  96.  
  97. if(city1.city == this.start){
  98. city2.capacityToStart = distance;
  99. city2.timeToStart = time;
  100. city2.parent = city1;
  101. queue.add(city2);
  102. }
  103. /*else if(city2.city == this.start){
  104. city1.capacityToStart = distance;
  105. city1.timeToStart = time;
  106. city1.parent = city2;
  107. queue.add(city1);
  108. }*/
  109. }
  110. in.close();
  111.  
  112. } catch (FileNotFoundException e) {
  113. // TODO Auto-generated catch block
  114. e.printStackTrace();
  115. }
  116.  
  117. }
  118.  
  119. public void solve(){
  120. this.cities.get(start).parent = null;
  121. this.cities.get(start).timeToStart = 0;
  122. this.cities.get(start).capacityToStart = 0;
  123. this.cities.get(start).visited = true;
  124.  
  125. while(!queue.isEmpty()){
  126. City c = queue.poll();
  127. c.visited = true;
  128.  
  129. for(Road r : c.roads){
  130. if(r.destination.visited == true)
  131. continue;
  132.  
  133. if(r.destination.capacityToStart >= r.capacity && r.destination.capacityToStart >= c.capacityToStart && r.destination.timeToStart > c.timeToStart + r.time ){
  134. r.destination.capacityToStart = max(r.capacity, c.capacityToStart);
  135. r.destination.timeToStart = c.timeToStart + r.time;
  136. r.destination.parent = c;
  137.  
  138. }
  139.  
  140. if(!queue.contains(r.destination))
  141. queue.add(r.destination);
  142.  
  143. break;
  144. }
  145.  
  146. if(c.city == destination)
  147. break;
  148. }
  149. /* Initializarea celorlalte costuri intiaile o fac la citire pentru eficientizare */
  150.  
  151. /*City c = cities.get(destination);
  152. while(c != null){
  153. System.out.print(c.city + " ");
  154. c = c.parent;
  155. }
  156. System.out.println();*/
  157. //System.out.println(cities.get(destination).capacityToStart + " " + cities.get(destination).timeToStart);
  158. }
  159.  
  160.  
  161.  
  162. private int max(int capacity, int capacityToStart) {
  163. return capacity > capacityToStart ? capacity : capacityToStart;
  164. }
  165.  
  166.  
  167. private void writeResult(String fileName) {
  168. PrintWriter out;
  169. try {
  170. out = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
  171. out.write(cities.get(destination).capacityToStart + " " + cities.get(destination).timeToStart);
  172. out.close();
  173. } catch (IOException e) {
  174. // TODO Auto-generated catch block
  175. e.printStackTrace();
  176. }
  177. }
  178.  
  179. public static void main(String[] args){
  180. Trip main = new Trip();
  181. main.readData("trip.in");
  182. main.solve();
  183. main.writeResult("trip.out");
  184. }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment