Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.FileNotFoundException;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.ArrayList;
- import java.util.Comparator;
- import java.util.PriorityQueue;
- import java.util.StringTokenizer;
- import java.util.logging.Level;
- import java.util.logging.Logger;
- class Pair extends Solution implements Comparator<Pair>{
- public int first;
- public int second;
- public Pair(Integer rt, Integer pr) { this.first = rt; this.second = pr; }
- public Pair(){
- first=-1;
- second=-1;
- }
- public static boolean same(Integer first, Integer second) {
- return first == null ? second == null : first.equals(second);
- }
- Integer getFirst() { return first; }
- Integer getSecond() { return second; }
- void setFirst(Integer o) { first = o; }
- void setSecond(Integer o) { second = o; }
- public boolean equals(Pair obj) {
- if( ! (obj instanceof Pair))
- return false;
- Pair p = (Pair)obj;
- return same(p.first, this.first) && same(p.second, this.second);
- }
- public String toString() {
- return "Pair{"+first+", "+second+"}";
- }
- public int compare(Pair o1, Pair o2) {
- return o2.second-o1.second;
- }
- };
- class Four extends Solution implements Comparator<Four>{
- public int first;
- public double second;
- public int third;
- public int four;
- public Four(int f, double s,int t,int fo){
- first = f;
- second = s;
- third = t;
- four = fo;
- }
- public Four(){
- first=-1;
- second=-1.0;
- third=-1;
- four = -1;
- }
- public int compare(Four o1, Four o2) {
- return (int)o1.second-(int)o2.second;
- }
- };
- public class Solution {
- public static ArrayList<ArrayList<ArrayList<Pair>>> matrix;
- public static int start;
- public static int finish;
- public static int num_of_cities;
- public static int num_of_roads;
- public static Pair nothing;
- public static void main(String arg[]) throws FileNotFoundException{
- matrix = new ArrayList< ArrayList< ArrayList< Pair >>>();
- nothing = new Pair(-1,-1);
- BufferedReader in = new BufferedReader(new FileReader("input.txt"));
- try{
- num_of_cities = Integer.parseInt(in.readLine());
- num_of_roads = Integer.parseInt(in.readLine());
- for(int i=0; i<num_of_cities ; i++)
- {
- ArrayList<ArrayList<Pair>> temp = new ArrayList<ArrayList<Pair>>();
- ArrayList<Pair> temp2 = new ArrayList<Pair>();
- temp2.add(nothing);
- for(int j=0;j<num_of_cities ; j++)
- {
- temp.add(temp2);
- }
- matrix.add(temp);
- }
- int road;
- int tocity;
- int fromcity;
- int coast;
- StringTokenizer str_tok;
- for(int i=0; i<num_of_roads; i++){
- str_tok = new StringTokenizer(in.readLine()," ");
- fromcity = Integer.parseInt(str_tok.nextToken());
- tocity = Integer.parseInt(str_tok.nextToken());
- road = Integer.parseInt(str_tok.nextToken());
- coast = Integer.parseInt(str_tok.nextToken());
- if(matrix.get(fromcity-1).get(tocity-1).get(0).second==-1){
- ArrayList<Pair> temp_arr = new ArrayList<Pair>();
- temp_arr.add(new Pair(road, coast));
- matrix.get(fromcity-1).set(tocity-1,temp_arr);
- matrix.get(tocity-1).set(fromcity-1,temp_arr);
- }
- else{
- matrix.get(fromcity-1).get(tocity-1).add(new Pair(road, coast));
- //matrix.get(tocity-1).get(fromcity-1).add(new Pair(road, coast));
- }
- }
- str_tok = new StringTokenizer(in.readLine()," ");
- start = Integer.parseInt(str_tok.nextToken());
- finish = Integer.parseInt(str_tok.nextToken());
- PrintWriter fout = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
- Four answer = cheepest_way();
- if(answer.first==finish){
- fout.println("Yes");
- fout.printf("%.2f",answer.second);
- }
- else{
- fout.print("No");
- }
- fout.close();
- } catch (IOException ex) {
- Logger.getLogger(Solution.class.getName()).log(Level.SEVERE, null, ex);
- }
- }
- public static Four cheepest_way(){
- PriorityQueue<Four> queue = new PriorityQueue<Four>(1000000, new Four());
- Four temp = new Four(start, 0.0, -1,0);
- Pair temp2 = new Pair();
- for(int i=0;i<num_of_cities;i++){
- temp2=(matrix.get(temp.first-1).get(i).get(0));
- if(temp2.first!=-1){
- for(int j=0;j<matrix.get(temp.first-1).get(i).size();j++){
- temp2=(matrix.get(temp.first-1).get(i).get(j));
- queue.add(new Four(i+1,(temp.second+(temp2.second+((double)temp2.second/10))),temp.first,j));
- }
- }
- }
- while(!queue.isEmpty()){
- temp = queue.poll();
- if(temp.first==finish)
- return temp;
- for(int i=0;i<num_of_cities;i++){
- temp2=(matrix.get(temp.first-1).get(i).get(0));
- if(temp2.second!=-1){
- for(int j=0;j<matrix.get(temp.first-1).get(i).size();j++){
- temp2=(matrix.get(temp.first-1).get(i).get(j));
- if(matrix.get(temp.first-1).get(temp.third-1).get(temp.four).first==temp2.first){
- queue.add(new Four(i+1,temp.second+temp2.second,temp.first,j));
- }
- else{
- queue.add(new Four(i+1,temp.second+
- (temp2.second+(temp2.second/10)),temp.first,j));
- }
- }
- }
- }
- for(int j=0;j<matrix.get(temp.third-1).get(temp.first-1).size();j++){
- int g = matrix.get(temp.third-1).get(temp.first-1).get(j).first;
- matrix.get(temp.third-1).get(temp.first-1).set(j,
- new Pair(g,-1));
- }
- }
- return temp;
- }
- }
Add Comment
Please, Sign In to add comment