[JAVA] Atcoder ABC70 D Problem

Aufgrund der Bedingungen war es ein Problem, dass der Worshall Floyd nicht verwendet werden konnte, und es war erforderlich, die DFS und die angrenzende Liste zu implementieren. Notieren Sie sich daher die Lösung

https://beta.atcoder.jp/contests/abc070/tasks/abc070_d

Betrachten Sie zunächst einen typischen Worshall Floyd. Worshall Floyd ist ein Algorithmus, der leicht den kürzesten Abstand zwischen zwei Punkten für alle Scheitelpunkte findet, wenn ein Diagramm vorhanden ist (alle Abstände sind positive Werte). Das Implementierungsbeispiel ist wie folgt

		int[][] dp = new int[n][n];
		
		for(int i = 0;i < n;i++){				//Eingang
			for(int j = 0;j < n;j++){
				int x = sc.nextInt();			//x ist der Abstand von i zu j
				dp[i][j] = x;
			}
		}

		for(int k = 0;k < n;k++){				//Worshall Floyd
			for(int i = 0;i < n;i++){
				for(int j = 0;j < n;j++){
					dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]);   //Aktualisieren Sie den kürzesten Abstand zwischen zwei Punkten an jedem Scheitelpunkt
				}
			}
		}

Dies ist sehr einfach zu implementieren, hat jedoch einen Nachteil: Die berechnete Zeit beträgt O (N ^ 3). Wenn also viele Eckpunkte vorhanden sind, wird sie bald zu TLE. Selbst bei diesem Problem tritt TLE mit einem Rand auf. Ziehen Sie daher eine andere Methode in Betracht, um die kürzeste Entfernung zu ermitteln. Wenn ich ruhig denke, lautet die Antwort auf diese Frage, dass es einen Scheitelpunkt k gibt, der passieren muss. Daher ist mir klar, dass dfs den kürzesten Abstand zwischen jedem Scheitelpunkt von k finden sollte. Selbst wenn alle Zeitberechnungen gezählt werden, ist es N (Gesamtzahl der Eckpunkte), sodass der Zeitberechnungsbetrag von dfs O (N) ist. Daher beträgt die Gesamtzeitberechnung O (Q + N), also O (Q + N), da die Anzahl der zu beantwortenden Fragen + O (N) beträgt.

Ein Beispiel für die Implementierung von dfs ist wie folgt

static void dfs(int p,long d){
		depth[p] = d;

		for(int i:graph.get(p).keySet()){				//Wenn Sie von Ihrem aktuellen Standort zu einem Ort wechseln können, den Sie nicht besucht haben, gehen Sie.
			if(!(used[i])){
				used[i] = true;
				dfs(i,  d + graph.get(p).get(i));
			}
		}
		return ;
	}
}

Als ich dieses Mal ein Diagramm erstellte, dachte ich zuerst an eine benachbarte Matrix (wie dp [] []), aber da es offensichtlich MLE von der Problembedingung ist, Hashmap <benachbarte Eckpunkte, Abstand> in ArrayList Ich habe eine Adjazenzliste erstellt, indem ich sie gesetzt habe. Diese Liste fungiert als benachbarte Liste, indem der Index von ArrayList als aktueller Scheitelpunkt festgelegt und an jedem Scheitelpunkt eine Hashmap eingefügt wird. Eine Sache, die Sie bei dieser Liste beachten sollten, ist, dass Sie vorerst alles in die ArrayList aufnehmen können. Fügen Sie also eine Hashmap in jeden Index ein. Ohne es zu tun

graph.get(a).put(b, c);		//Geben Sie den Startpunkt mit get, put an<Benachbarte Punkte, Entfernung>ich werde legen

In diesem Fall tritt ein Fehler auf. Sie müssen auch vorsichtig sein, wenn Sie die Hashmap zu Beginn einfügen.

 HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
	for(int i = 0; i <= n;i++){
			zero.put(0, 0);
			graph.add(i, zero);					//Geben Sie den Startpunkt mit get, put an<Benachbarte Punkte, Entfernung>ich werde legen
	}

Wenn Sie auf diese Weise dieselbe Hashmap in jeden Index von ArrayList einfügen, wird diese Hashmap allen Indizes hinzugefügt, unabhängig davon, zu welchem Index Sie eine neue Hashmap hinzufügen. Daher müssen Sie wie folgt vorgehen

		for(int i = 0; i <= n;i++){
			HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
			zero.put(0, 0);
			graph.add(i, zero);					//Geben Sie den Startpunkt mit get, put an<Benachbarte Punkte, Entfernung>ich werde legen
		}