Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedWriter;
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.ArrayList;
- import java.util.PriorityQueue;
- import java.util.Scanner;
- import java.util.Comparator;
- class Road{
- City destination;
- int capacity;
- int time;
- public Road(City destination, int cost, int time){
- this.destination = destination;
- this.capacity = cost;
- this.time = time;
- }
- public String toString(){
- return this.destination + ": " + "Capacity: " + this.capacity + "- Time: " + this.time;
- }
- }
- class City{
- PriorityQueue<Road> roads = new PriorityQueue<Road>(10, new Comparator<Road>(){
- public int compare(Road r1, Road r2) {
- return r1.capacity - r2.capacity == 0 ? r1.time - r2.time : r1.capacity - r2.capacity;
- }
- });
- public City(int city){
- this.city = city;
- }
- public String toString(){
- return this.city + "";
- }
- int city;
- int capacityToStart = 1<<31-1;
- int timeToStart = 1<<31-1;
- boolean visited = false;
- City parent;
- }
- class Trip{
- int numberOfCities, numberOfRoads;
- int start, destination;
- PriorityQueue<City> queue;
- ArrayList<City> cities;
- public void readData(String fileName){
- Scanner in;
- try {
- in = new Scanner(new File(fileName));
- numberOfCities = in.nextInt();
- cities = new ArrayList<City>(numberOfCities);
- for(int i=0; i<numberOfCities; i++)
- cities.add(new City(i));
- Comparator<City> c = new Comparator<City>(){
- @Override
- public int compare(City city1, City city2) {
- return city1.capacityToStart - city2.capacityToStart == 0 ? city1.timeToStart - city2.timeToStart : city1.capacityToStart - city2.capacityToStart;
- }
- };
- queue = new PriorityQueue<City>(10, c);
- numberOfRoads = in.nextInt();
- start = in.nextInt();
- destination = in.nextInt();
- while(in.hasNext()){
- City city1 = cities.get(in.nextInt());
- City city2 = cities.get(in.nextInt());
- int distance = in.nextInt();
- int time = in.nextInt();
- //Road r1 = new Road(city1, distance, time);
- Road r2 = new Road(city2, distance, time);
- city1.roads.add(r2);
- //city2.roads.add(r1);
- if(city1.city == this.start){
- city2.capacityToStart = distance;
- city2.timeToStart = time;
- city2.parent = city1;
- queue.add(city2);
- }
- /*else if(city2.city == this.start){
- city1.capacityToStart = distance;
- city1.timeToStart = time;
- city1.parent = city2;
- queue.add(city1);
- }*/
- }
- in.close();
- } catch (FileNotFoundException e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- public void solve(){
- this.cities.get(start).parent = null;
- this.cities.get(start).timeToStart = 0;
- this.cities.get(start).capacityToStart = 0;
- this.cities.get(start).visited = true;
- while(!queue.isEmpty()){
- City c = queue.poll();
- c.visited = true;
- for(Road r : c.roads){
- if(r.destination.visited == true)
- continue;
- if(r.destination.capacityToStart >= r.capacity && r.destination.capacityToStart >= c.capacityToStart && r.destination.timeToStart > c.timeToStart + r.time ){
- r.destination.capacityToStart = max(r.capacity, c.capacityToStart);
- r.destination.timeToStart = c.timeToStart + r.time;
- r.destination.parent = c;
- }
- if(!queue.contains(r.destination))
- queue.add(r.destination);
- break;
- }
- if(c.city == destination)
- break;
- }
- /* Initializarea celorlalte costuri intiaile o fac la citire pentru eficientizare */
- /*City c = cities.get(destination);
- while(c != null){
- System.out.print(c.city + " ");
- c = c.parent;
- }
- System.out.println();*/
- //System.out.println(cities.get(destination).capacityToStart + " " + cities.get(destination).timeToStart);
- }
- private int max(int capacity, int capacityToStart) {
- return capacity > capacityToStart ? capacity : capacityToStart;
- }
- private void writeResult(String fileName) {
- PrintWriter out;
- try {
- out = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
- out.write(cities.get(destination).capacityToStart + " " + cities.get(destination).timeToStart);
- out.close();
- } catch (IOException e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- public static void main(String[] args){
- Trip main = new Trip();
- main.readData("trip.in");
- main.solve();
- main.writeResult("trip.out");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment