Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Nov 16th, 2018 73 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import java.util.*;
  2. public class Reitit {
  3.  
  4.     private HashMap<String, Solmu> verkko = new HashMap<>();
  5.  
  6.     public class Kaari {
  7.         public String alku, loppu;
  8.         int pituus;
  9.  
  10.         public Kaari(String alku, String loppu, int pituus) {
  11.             this.alku = alku;
  12.             this.loppu = loppu;
  13.             this.pituus = pituus;
  14.         }
  15.     }
  16.  
  17.     public class Solmu implements Comparable<Solmu> {
  18.         public final String nimi;
  19.         public int etaisyys = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
  20.         public Solmu edellinen = null;
  21.         public final Map<Solmu, Integer> naapurit = new HashMap<>();
  22.  
  23.         public Solmu(String nimi) {
  24.             this.nimi = nimi;
  25.         }
  26.  
  27.         public int compareTo(Solmu toinen) {
  28.             if (etaisyys == toinen.etaisyys)
  29.                 return nimi.compareTo(toinen.nimi);
  30.             return Integer.compare(etaisyys, toinen.etaisyys);
  31.         }
  32.  
  33.     }
  34.  
  35.     List<Kaari> kaaret = new ArrayList<>(10000);
  36.  
  37.     @SuppressWarnings("Duplicates")
  38.     public void lisaaTie(String alku, String loppu, int pituus) {
  39.         Kaari kaari1 = new Kaari(alku, loppu, pituus);
  40.         Kaari kaari2 = new Kaari(loppu, alku, pituus);
  41.  
  42.         kaaret.add(kaari1);
  43.         kaaret.add(kaari2);
  44.     }
  45.  
  46.     public int reitinPituus(String alku, String loppu) {
  47.         luoVerkko();
  48.         dijkstra(alku);
  49.         return lyhyinPolku(loppu);
  50.     }
  51.  
  52.     private void luoVerkko() {
  53.  
  54.         verkko = new HashMap<>(kaaret.size());
  55.  
  56.         for( Kaari kaari : kaaret) {
  57.             if( !verkko.containsKey(kaari.alku)) verkko.put(kaari.alku, new Solmu(kaari.alku));
  58.             if( !verkko.containsKey(kaari.loppu)) verkko.put(kaari.loppu, new Solmu(kaari.loppu));
  59.         }
  60.         for( Kaari kaari : kaaret) {
  61.             verkko.get(kaari.alku).naapurit.put(verkko.get(kaari.loppu), kaari.pituus);
  62.         }
  63.     }
  64.  
  65.  
  66.     public void dijkstra(String alku) {
  67.         if (!verkko.containsKey(alku)) {
  68.             System.err.printf("Verkossa ei ole solmua\"%s\"\n", alku);
  69.             return;
  70.         }
  71.         final Solmu source = verkko.get(alku);
  72.         NavigableSet<Solmu> q = new TreeSet<>();
  73.  
  74.         // set-up vertices
  75.         for (Solmu v : verkko.values()) {
  76.             v.edellinen = v == source ? source : null;
  77.             v.etaisyys = v == source ? 0 : Integer.MAX_VALUE;
  78.             q.add(v);
  79.         }
  80.  
  81.         dijkstra(q);
  82.     }
  83.  
  84.     private void dijkstra(final NavigableSet<Solmu> q) {
  85.         Solmu u, v;
  86.         while (!q.isEmpty()) {
  87.  
  88.             u = q.pollFirst();
  89.             if (u.etaisyys == Integer.MAX_VALUE)
  90.                 break;
  91.  
  92.             for (Map.Entry<Solmu, Integer> a : u.naapurit.entrySet()) {
  93.                 v = a.getKey(); //the neighbour in this iteration
  94.  
  95.                 final int alternateDist = u.etaisyys + a.getValue();
  96.                 if (alternateDist < v.etaisyys) {
  97.                     q.remove(v);
  98.                     v.etaisyys = alternateDist;
  99.                     v.edellinen = u;
  100.                     q.add(v);
  101.                 }
  102.             }
  103.         }
  104.     }
  105.  
  106.     public int lyhyinPolku(String loppu) {
  107.         if (!verkko.containsKey(loppu)) {
  108.  
  109.             return -1;
  110.         }
  111.  
  112.         return verkko.get(loppu).etaisyys;
  113.     }
  114.  
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top