[JAVA] Problème atcoder ABC70 D

En raison des conditions, c'était un problème que le Worshall Floyd ne pouvait pas être utilisé et il était nécessaire d'implémenter DFS et la liste adjacente, alors prenez note de la solution.

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

Tout d'abord, considérons un Worshall Floyd typique. Worshall Floyd est un algorithme qui trouve facilement la distance la plus courte entre deux points pour tous les sommets lorsqu'il y a un graphe (toutes les distances sont des valeurs positives). L'exemple de mise en œuvre est comme ci-dessous

		int[][] dp = new int[n][n];
		
		for(int i = 0;i < n;i++){				//contribution
			for(int j = 0;j < n;j++){
				int x = sc.nextInt();			//x est la distance de i à 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]);   //Mettre à jour la distance la plus courte entre deux points à chaque sommet
				}
			}
		}

C'est très facile à mettre en œuvre, mais cela présente un inconvénient: le temps calculé est O (N ^ 3), donc s'il y a beaucoup de sommets, il deviendra bientôt TLE. Même avec ce problème, TLE se produira avec une marge, envisagez donc une méthode différente pour trouver la distance la plus courte. En réfléchissant calmement, la réponse à cette question est qu'il y a un sommet k qui doit passer, donc je me rends compte que la distance la plus courte entre chaque sommet de k doit être trouvée par dfs. Puisque la quantité de calcul de temps est N (nombre total de sommets) même si tous sont comptés, la quantité de calcul de temps de dfs est O (N). Par conséquent, le temps total de calcul est O (Q + N), qui est O (Q + N), car le nombre de questions auxquelles il faut répondre est + O (N).

Un exemple d'implémentation de dfs est comme ci-dessous

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

		for(int i:graph.get(p).keySet()){				//Si vous pouvez passer de votre position actuelle à un endroit que vous n'avez pas visité, allez-y.
			if(!(used[i])){
				used[i] = true;
				dfs(i,  d + graph.get(p).get(i));
			}
		}
		return ;
	}
}

Aussi, lors de la création d'un graphique cette fois, j'ai d'abord pensé à une matrice adjacente (comme dp [] []), mais comme il s'agit évidemment de MLE de la condition du problème, Hashmap <sommets adjacents, distance> dans ArrayList J'ai fait une liste de contiguïté en mettant. Cette liste fonctionne comme une liste adjacente en définissant l'index de ArrayList en tant que sommet courant et en insérant Hashmap à chaque sommet. Une chose à noter à propos de cette liste est que vous pouvez mettre n'importe quoi dans ArrayList pour le moment, alors mettez un Hashmap dans chaque index. Sans le faire

graph.get(a).put(b, c);		//Spécifiez le point de départ avec get, put<Points adjacents, distance>Je mettrai

Si vous le faites, une erreur se produira. Vous devez également faire attention lorsque vous insérez le Hashmap au début.

 HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
	for(int i = 0; i <= n;i++){
			zero.put(0, 0);
			graph.add(i, zero);					//Spécifiez le point de départ avec get, put<Points adjacents, distance>Je mettrai
	}

Si vous mettez le même Hashmap dans chaque index de ArrayList de cette manière, ce Hashmap sera ajouté à tous les index, quel que soit l'index auquel vous ajoutez un nouveau Hashmap. Par conséquent, vous devez faire comme ci-dessous

		for(int i = 0; i <= n;i++){
			HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
			zero.put(0, 0);
			graph.add(i, zero);					//Spécifiez le point de départ avec get, put<Points adjacents, distance>Je mettrai
		}