[JAVA] ABC --022 --A & B & C

AtCoder ABC 022 A&B&C AtCoder - 022

** 2019/05/14 postscript ** Problem B: Code modification to get the total of res

A problem

--Check if your weight is within the proper range for each uptake

	private void solveA() {
		int n = nextInt();
		int s = nextInt();
		int t = nextInt();
		int w = nextInt();

		long sum = w;
		int res = 0;
		for (int i = 0; i < n; i++) {
			if (i != 0) {
				sum += nextInt();
			}
			if (s <= sum && sum <= t) {
				res++;
			}
		}

		out.println(res);
	}

B problem

(2019/05/14 Code correction to get the total of res)

--You can see the following by reading the problem statement -Cannot pollinate when there is only one flower of a certain type --Two or more flowers pollinate n-1 --Three flowers pollinate two

--Count two or more flowers --Each flower pollinates n-1 so count

--Commented out works as well. Some trials to confirm how to write

		int numN = nextInt();

		Map<Integer, Long> tmp = IntStream.range(0, numN).map(i -> nextInt()).mapToObj(i -> new Integer(i))
				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));

		long res = tmp.values().stream().mapToLong(i -> i - 1).sum();

		//		long res = tmp.values().stream().filter(i -> i.longValue() > 1).reduce(0L, (sum, i) -> sum += (i - 1));

		//		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		//		Map<Integer, Long> tmp = Arrays.stream(wk).mapToObj(i -> new Integer(i))
		//				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
		//		long res = tmp.values().stream().filter(i -> i.longValue() > 1).reduce(0L, (sum, i) -> sum += (i - 1));

		out.println(res);

Problem C: Floyd-Warshall Floyd method

――Get out of 1 and come back to 1 ――However, you cannot use the same road --The vertices adjacent to 1 need to be changed on the outbound and inbound journeys -Find the shortest path between vertices adjacent to 1 and calculate the following movement cost --1-> Adjacent vertices 1-> Adjacent vertices 2-> 1 --Brute force for adjacent vertices 1-2 -Use ** Floyd-Warshall Floyd method ** to calculate [Adjacent Vertex 1-> Adjacent Vertex 2] -When calculating [Adjacency Vertex 1-> Adjacency Vertex 2], it passes through the same place twice via [1], so I created an adjacency matrix with the cost of 1 omitted.

--Calculation result of graphWithOutStart based on Example 1 (Calculation result of adjacency matrix cormorant without vertex 1) --All are tINF because they do not pass through vertex 1.

--For comparison: Graph calculation result based on Example 1 (minimum cost calculation result for each vertex)

	private void solveC() {
		final long CONST_INF = Long.MAX_VALUE / 10;

		int n = nextInt();
		int m = nextInt();
		long[][] graphWithOutStart = new long[n][n];
		long[][] graph = new long[n][n];
		List<Integer> edgeNearByStart = new ArrayList<Integer>();

		/*
		 *graph initialization
		 * [1]With adjacency matrix including[1]Creating an adjacency matrix without
		 */
		for (int i = 0; i < n; i++) {
			Arrays.fill(graph[i], CONST_INF);
			Arrays.fill(graphWithOutStart[i], CONST_INF);
			graphWithOutStart[i][i] = 0;
			graph[i][i] = 0;
		}

		for (int i = 0; i < m; i++) {

			/*
			 *According to the subscript-1 and capture
			 */
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			int cost = nextInt();
			if (from != 0) {
				/*
				 * [1]Graph excluding
				 */
				graphWithOutStart[from][to] = cost;
				graphWithOutStart[to][from] = cost;
			} else {
				/*
				 * [1]Adjacent vertices to
				 */
				edgeNearByStart.add(to);
			}
			graph[from][to] = cost;
			graph[to][from] = cost;
		}

		long res = Long.MAX_VALUE;

		Collections.sort(edgeNearByStart);

		/*
		 *Warshall – Floyd method to update vertices
		 */

		getMinByWarshall(graphWithOutStart, n);

		for (int i = 0; i < edgeNearByStart.size(); i++) {
			for (int j = i + 1; j < edgeNearByStart.size(); j++) {
				int start = edgeNearByStart.get(i);
				int end = edgeNearByStart.get(j);
				/*
				 * [1]From[Adjacent vertices 1]Cost+ [Adjacent vertices 1][Adjacent vertices 2]Cost+ [Adjacent vertices 2]From[1]Cost
				 */
				long total = graph[0][start] + graphWithOutStart[start][end] + graph[0][end];
				//Adopt low value
				res = Long.min(res, total);
			}

		}

		out.println(res >= CONST_INF ? -1 : res);

	}

	/**
	 *
	 * @param edge
	 * @param point
	 */
	private void getMinByWarshall(long[][] edge, int point) {
		for (int k = 0; k < point; k++) {
			for (int i = 0; i < point; i++) {
				for (int j = 0; j < point; j++) {
					edge[i][j] = Long.min(edge[i][j], edge[i][k] + edge[k][j]);
				}
			}
		}

	}

Problem C: Floyd-Warshall Floyd method (short code version)

-When calculating [adjacent vertex 1-> adjacent vertex 2], since it passes through the same place twice via [1], I created an adjacency matrix that omits the cost of 1, but the Worshall Floyd If you start the subscript from [1] instead of [0], you can calculate the cost without going through [Vertex 1]. .. .. ――By using this, you can calculate by the Floyd-Warshall method without creating an adjacency matrix that omits vertex 1, which speeds up and is easy to see.

--The table below shows the results calculated by the Floyd-Warshall method from the subscript [1] with Example 1. --The cost of moving to 1 is calculated for the vertices (2,4,5) adjacent to 1, but the cost is not calculated for the vertices (3) that are not adjacent to 1. --The minimum cost from vertex 2 to vertex 4 is 3, but the calculated result is the cost of moving the vertex [2-> 5-> 3-> 4] to 10.

--For comparison: When calculated from subscript [1] and when calculated from subscript [0] --The table below calculates the adjacency matrix without vertex 1 from the subscript [0].

	private void solveC() {
		final long CONST_INF = Long.MAX_VALUE / 10;

		int n = nextInt();
		int m = nextInt();
		long[][] graph = new long[n][n];

		/*
		 *graph initialization
		 * [1]With adjacency matrix including[1]Creating an adjacency matrix without
		 */
		for (int i = 0; i < n; i++) {
			Arrays.fill(graph[i], CONST_INF);
			graph[i][i] = 0;
		}

		for (int i = 0; i < m; i++) {

			/*
			 *According to the subscript-1 and capture
			 */
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			int cost = nextInt();
			graph[from][to] = cost;
			graph[to][from] = cost;
		}

		long res = Long.MAX_VALUE;

		/*
		 *Warshall – Floyd method to update vertices
		 */

		/*
		 *If you start the subscript from 1, it will not be updated for 1
		 */
		for (int k = 1; k < n; k++) {
			for (int i = 1; i < n; i++) {
				for (int j = 1; j < n; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}

		for (int i = 1; i < n; i++) {
			for (int j = 1; j < n; j++) {
				if (i != j) {
					res = Math.min(res, graph[0][i] + graph[i][j] + graph[j][0]);
				}
			}
		}

		out.println(res >= CONST_INF ? -1 : res);

	}