import java.util.*;

class Kante{
	  Knoten ziel;
	  int laenge;
	  Kante (Knoten k, int l){ziel=k; laenge=l;}
	} 

class Knoten{
    String  name;
    private int marken;
    ArrayList<Kante> nachbarn;
    Knoten(String s){ name = s; nachbarn = new ArrayList<Kante>();}
    boolean isMarked(){return marken > 0;}
    int getMarken(){return marken;}
    void resetMarken(){marken=0;}
    void setMarked(){marken=1;}
    void incMarken(){marken++;}
    void decMarken(){marken--;}
    public String toString(){ return name;}
}

class Graph{
	  
	  int knotenZahl;
    Knoten[] knotenArray; 
    private final int ariMax = 2;
	  private int aktSchranke;
	  LinkedList<Kante> aktTSP;
	  Knoten ausgangsKnoten;
	  HashSet<Knoten> s = new HashSet<Knoten>(); 
    
    Graph(){
    	Knoten sFra = new Knoten("San Francisco"), sRaf = new Knoten("San Rafael"), 
	           rich = new Knoten("Richmond"),      oakl = new Knoten("Oakland"), 
	           sMat = new Knoten("San Mateo"),     hayw = new Knoten("Hayward"),
	           palo = new Knoten("Palo Alto"),     frem = new Knoten("Fremont"), 
	           sJos = new Knoten("San Jose"),      sCla = new Knoten("Santa Clara"),
	           scot = new Knoten("Scotts Valley"), wats = new Knoten("Watsonville"),
	           sCru = new Knoten("Santa Cruz"),    half = new Knoten("Half Moon Bay"),
	           paci = new Knoten("Pacifica");
           
      Knoten[] ka = {sFra,sRaf,rich,oakl,sMat,hayw,palo,frem,sJos,sCla,scot,wats,sCru,half,paci};
		  knotenArray = ka;
		  knotenZahl  = ka.length;
	    
	     //Kanten definieren
	    sFra.nachbarn.add(new Kante(sRaf,18));
	    sFra.nachbarn.add(new Kante(oakl,12));
	    sFra.nachbarn.add(new Kante(sMat,20));
	    sFra.nachbarn.add(new Kante(paci,15));
	    
	    sRaf.nachbarn.add(new Kante(sFra,18));
	    sRaf.nachbarn.add(new Kante(rich,15));
	    
	    rich.nachbarn.add(new Kante(sRaf,15));
	    rich.nachbarn.add(new Kante(oakl,15));
	    
	    oakl.nachbarn.add(new Kante(sFra,12));
	    oakl.nachbarn.add(new Kante(rich,15));
	    oakl.nachbarn.add(new Kante(hayw,20));
	    
	    sMat.nachbarn.add(new Kante(sFra,20));
	    sMat.nachbarn.add(new Kante(hayw,20));
	    sMat.nachbarn.add(new Kante(palo,18));
	    sMat.nachbarn.add(new Kante(half,25));
	    
	    hayw.nachbarn.add(new Kante(oakl,20));
	    hayw.nachbarn.add(new Kante(sMat,20));
	    hayw.nachbarn.add(new Kante(frem,14));
	    
	    palo.nachbarn.add(new Kante(sMat,18));
	    palo.nachbarn.add(new Kante(frem,15));
	    palo.nachbarn.add(new Kante(sCla,10));
	    
	    frem.nachbarn.add(new Kante(hayw,14));
	    frem.nachbarn.add(new Kante(palo,15));
	    frem.nachbarn.add(new Kante(sJos,20));  
	    
	    sJos.nachbarn.add(new Kante(frem,20));
	    sJos.nachbarn.add(new Kante(sCla,15));
	    sJos.nachbarn.add(new Kante(wats,60));
	    
	    sCla.nachbarn.add(new Kante(palo,10));
	    sCla.nachbarn.add(new Kante(sJos,15));
	    sCla.nachbarn.add(new Kante(scot,35));
	    
	    scot.nachbarn.add(new Kante(sCla,35));
	    scot.nachbarn.add(new Kante(sCru,10));
	    
	    wats.nachbarn.add(new Kante(sJos,60));
	    wats.nachbarn.add(new Kante(sCru,70));
	    
	    sCru.nachbarn.add(new Kante(scot,10));
	    sCru.nachbarn.add(new Kante(wats,70));
	    sCru.nachbarn.add(new Kante(half,50));
 
	    half.nachbarn.add(new Kante(sCru,50));
	    half.nachbarn.add(new Kante(sMat,25));
	    half.nachbarn.add(new Kante(paci,15));
	    
	    paci.nachbarn.add(new Kante(half,15));
	    paci.nachbarn.add(new Kante(sFra,15));
	  }

 void resetMarken(){for (Knoten k : knotenArray) k.resetMarken();}
    
    
    int index(Knoten k){
    	  for (int i=0; i < knotenZahl; i++)
            if (k == knotenArray[i]) return i;
        return -1;    
        }    
    
    int index(String s){
    	  for (int i=0; i < knotenZahl; i++)
            if (s.equals(knotenArray[i].name)) return i;
        return -1;    
        }
        
    Knoten find(String s){
    	  for (int i=0; i < knotenZahl; i++)
            if (s.equals(knotenArray[i].name)) return knotenArray[i];
        return null;    
        }    
    
    int kante(int k1, Knoten k2){
    	  for (Kante k : knotenArray[k1].nachbarn)
            if (k.ziel == k2) return k.laenge;
        return -1;    
        }
        
    int kante(Knoten k1, Knoten k2){
    	  for (Knoten i1 : knotenArray)
    	    if (i1 == k1) for (Kante k : k1.nachbarn)
    	       if (k.ziel == k2) return k.laenge;
        return -1;    
        }           

    void nachbarn(){
    	for (Knoten k1 : knotenArray)
    	  for (Kante k : k1.nachbarn)
    		  System.out.println("Kante von "+k1+" nach "+k.ziel+" vorhanden. Länge ist: "+k.laenge);
    		}       
    
    private boolean testeWeg(Knoten v, LinkedList<Kante> aktWeg){
    	int l = 0;
    	int anz = 1; // Ausgangsknoten mitzählen!
    	for (Kante ka : aktWeg) { l+=ka.laenge; anz++;}
    	
    	if (l >= aktSchranke) return true; // Zu lang; nicht  weiter verlängern!
    	if (anz < knotenZahl) return false; // noch nicht alle Knoten besucht; weitermachen
    	if (aktWeg.getLast().ziel == v){// neue kürzere Lösung gefunden, falls ariMax ==1
    	   if (ariMax > 1){ // falls ariMax > 1 muss noch getestet werden, ob alle Knoten bis auf den Ausgangsknoten im Weg enthalten sind
    		    s.clear(); //optimiert: new sparen; HashSet<Knoten> s = new HashSet<Knoten>(); 
    		    s.add(ausgangsKnoten);
    		    for (Kante ka : aktWeg) s.add(ka.ziel);
    		    if (s.size() < knotenZahl) return false;
    		    } 
    	   aktSchranke = l;
    	   aktTSP = new LinkedList<Kante>(aktWeg);
    	   return true;
    		 }
    	return false;
     }
    	
    private void besuche(Knoten k, Knoten v, LinkedList<Kante> aktWeg){
    	k.incMarken();
    	for(Kante ka : k.nachbarn)
    	  if(ka.ziel.getMarken()< ariMax) {
	    		aktWeg.add(ka);
	    		if (!testeWeg(v, aktWeg)) besuche(ka.ziel,v,aktWeg);
	    		aktWeg.removeLast();
    	}
    	k.decMarken(); 
    }
    
    
    void tsp(Knoten u, Knoten v){
        aktSchranke = 370; // experimentell
        aktTSP = null;
        ausgangsKnoten = u;
        LinkedList<Kante> weg = new LinkedList<Kante>();
        long zeit1 = System.nanoTime();
        besuche(u, v, weg);
        long zeit2 = System.nanoTime();
        long milliZeit = (zeit2-zeit1)/1000000; 
        System.out.println("LaufZeit: "+milliZeit+" MilliSekunden");
        if ( aktTSP == null){
          System.out.println("Kein Weg gefunden !!!");
          return;
          }
        System.out.println("Länge des kürzesten Weges: "+ aktSchranke);
        System.out.println("Der kürzeste Weg ist: ");
        System.out.println(u);
        for(Kante ka: aktTSP) System.out.println(ka.ziel);       
    }
}

public class GraphT {

    static String start = "San Francisco";
    static String ziel = "San Mateo";
    
    public static void main(String args[]) {
        System.out.println("Graph Tester");
        Graph  g = new Graph();
        Knoten k1 = g.find(start);
        if (k1 == null) {System.out.println("Knoten " + start + " nicht im Graph gefunden!");return;}
        Knoten k2 = g.find(ziel);
        if (k2 == null) {System.out.println("Knoten " + ziel + " nicht im Graph gefunden!");return;}
 
	      g.tsp(k1,k2);
   }
}