atcoder ABC70 D problem

Due to the conditions, it was a problem that the Worshall Floyd could not be used and it was necessary to implement DFS and adjacency list, so make a note of the solution.

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

First, consider a typical Floyd-Warshall Floyd. Floyd-Warshall Floyd is an algorithm that easily finds the shortest distance between two points for all vertices when there is a graph (all distances are positive values). Implementation example is as below

		int[][] dp = new int[n][n];
		
		for(int i = 0;i < n;i++){				//input
			for(int j = 0;j < n;j++){
				int x = sc.nextInt();			//x is the distance from i to 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]);   //Update the shortest distance between two points at each vertex
				}
			}
		}

This is very easy to implement, but it has one drawback: the time complexity is O (N ^ 3), so if there are many vertices, it will soon become TLE. Even with this problem, TLE will occur with a margin, so consider a different method to find the shortest distance. Thinking calmly, the answer to this question is that there is a vertex k that must pass, so I realize that the shortest distance between each vertex from k should be calculated by dfs. Since the time complexity is N (total number of vertices) even if all are counted, the time complexity of dfs is O (N). Therefore, the total time complexity is O (Q + N), which is O (Q + N), because the number of questions that must be answered is + O (N).

An implementation example of dfs is as below

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

		for(int i:graph.get(p).keySet()){				//If you can go from your current location to a place you haven't visited, go.
			if(!(used[i])){
				used[i] = true;
				dfs(i,  d + graph.get(p).get(i));
			}
		}
		return ;
	}
}

Also, when making a graph this time, I first thought about an adjacency matrix (like dp [] []), but since it is obviously MLE from the problem condition, Hashmap <adjacency vertices, distance> in ArrayList I made an adjacency list by putting. This list functions as an adjacency list by setting the index of the ArrayList as the current vertex and inserting a Hashmap at each vertex. One thing to note about this list is that you can put anything in the ArrayList for the time being, so put one Hashmap in every index. Without doing so

graph.get(a).put(b, c);		//Specify the start point with get, put<Adjacent points, distance>I will put

If you do, an error will occur. You also need to be careful when inserting the Hashmap at the beginning.

 HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
	for(int i = 0; i <= n;i++){
			zero.put(0, 0);
			graph.add(i, zero);					//Specify the start point with get, put<Adjacent points, distance>I will put
	}

If you put the same Hashmap in each index of ArrayList in this way, this Hashmap will be added to all indexes no matter which index you add a new Hashmap to. Therefore, you have to do as below

		for(int i = 0; i <= n;i++){
			HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
			zero.put(0, 0);
			graph.add(i, zero);					//Specify the start point with get, put<Adjacent points, distance>I will put
		}