Jinnie Park

/* 문제설명 */

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

/* 풀이방법 */

다익스트라 알고리즘에 PriorityQueue를 합친 방식으로 해결하였다.

시작점을 (0,0)로 설정해주고 연결되어있는 (1,0),(0,1)을 우선순위큐에 추가해주었다.

그 뒤로 큐에서 하나 꺼내고, 4방향을 탐색후, 일단 방문체크를 해준다음에

만약에 최소비용를 갱신한다면 큐에 다시 넣어주는 것을 반복했다.

(n-1,n-1)에 도달한다면 큐를 빠져나오고 print를 하게 된다.

https://jinniepark.tistory.com/66

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//녹색 옷 입은 애가 젤다지?
public class b4485 {
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int testCase = 1;
		while(true) {
			
			int N = Integer.parseInt(br.readLine());
			if(N==0)break;
			
			int[][] cave = new int[N][N];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					cave[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			boolean[][] visited = new boolean[N][N];
			int[][] minDist = new int[N][N];
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					minDist[i][j] = 10000;
				}
			}	
			visited[0][0]=true;
			visited[0][1]=true;
			visited[1][0]=true;
			minDist[0][0]=cave[0][0];
			minDist[1][0]=cave[1][0]+cave[0][0];
			minDist[0][1]=cave[0][1]+cave[0][0];
			PriorityQueue<Area> pq = new PriorityQueue<>();
			pq.add(new Area(0,1,minDist[0][1]));
			pq.add(new Area(1,0,minDist[1][0]));

			while(!pq.isEmpty()) {
				Area a = pq.poll();
				
				if(a.r==N-1&&a.c==N-1) {
					System.out.printf("Problem %d: %d\n",testCase++,minDist[N-1][N-1]);
					break;
				}
				
				for(int d=0;d<4;d++) {
					int nx = a.r+dx[d];
					int ny = a.c+dy[d];
					if(nx>=0&&nx<N&&ny>=0&&ny<N&&!visited[nx][ny]) {
						visited[nx][ny]=true;
						if(minDist[nx][ny]>minDist[a.r][a.c]+cave[nx][ny]) {
							minDist[nx][ny]=minDist[a.r][a.c]+cave[nx][ny];
							pq.add(new Area(nx,ny,minDist[nx][ny]));
						}
					}
				}
			}
		}
	}
	public static class Area implements Comparable<Area>{
		int r;
		int c;
		int rupee;
		public Area(int r, int c, int rupee) {
			super();
			this.r = r;
			this.c = c;
			this.rupee = rupee;
		}
		@Override
		public int compareTo(Area o) {
			return Integer.compare(this.rupee, o.rupee);
		}
	}
}

다익스트라 알고리즘

한 정점으로 부터 모든 정점으로의 최단거리를 구하는 알고리즘이다. 

다만 음의 간선이 있다면 사용할 수 없다. 

동작 순서는 일단 출발지를 정하고, 이어져 있는 거리를 저장한다.

그 다음 부터는 가장 짧은 거리에 있는 정점을 방문하고, 해당 정점을 거쳐가는 거리가 더 짧다면 갱신, 아니면 그대로 둔다.

이런식으로 반복해서 모든 정점을 방문하면 끝나게 된다.

그래프와 인접그래프

다익스트라 알고리즘 시작!

추가적으로,, 최적화에 대해 생각해본다면, 가장 짧은 거리를 탐색할 때, 우선순위 큐를 활용한다면 O(nlogN)으로 탐색이 가능하다. 

관련문제

https://www.acmicpc.net/problem/4485

https://jinniepark.tistory.com/67

/* 문제설명 */

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

/* 풀이방법 */

이름처럼 플로이드 알고리즘으로 풀면 된다.

https://jinniepark.tistory.com/59?category=956229

다만, 문제를 똑바로 안읽어서 방문할 수 없는 노드를 0으로 고쳐야하는데 무한대로 놨다가 애를 먹었다.

문제를 제발 똑바로 읽자.

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//플로이드
public class b11404 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine()); // 도시(정점)
		int M = Integer.parseInt(br.readLine()); // 버스(간선)
		int[][] map = new int[N + 1][N + 1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				map[i][j] = -1;
			}
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()); // 출발
			int b = Integer.parseInt(st.nextToken()); // 도착
			int c = Integer.parseInt(st.nextToken()); // 비용
			if(map[a][b]==-1) {
				map[a][b] = c;
			}else {
				map[a][b] = Math.min(map[a][b], c);
			}
			
		}	
		
        //플로이드 알고리즘
		for (int n = 1; n <= N; n++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if(map[i][n]==-1||map[n][j]==-1) {
						continue;
					}
					if(map[i][j]==-1||map[i][j]>map[i][n]+map[n][j]) {
						map[i][j]=map[i][n]+map[n][j];
					}
				}
			}
		}
		
        //출력
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if(map[i][j]==-1||i==j)
					map[i][j] = 0;
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
	}
}

플로이드-와샬 알고리즘(이하 플로이드 알고리즘)은 최단 경로를 구하는 알고리즘이다.

이미 잘 알고있는 다익스트라 알고리즘은 한 점점으로 부터 다른 모든 정점으로의 최단 거리를 구할 수 있다.

하지만 플로이드 알고리즘은 모든 정점으로부터 모든 정점으로의 최단 거리를 구하는 알고리즘이다.

기본적으로 그래프를 일단 나타내고, 순차적으로 어떠한 정점을 거쳤을 때, 이동하는 비용이 줄어든다면 값을 고치는것을 반복하는 알고리즘이다. 

중요한건 (A에서 B로 가는 거리) > (A에서C를 들렀다가 B로 가는거리)이면 작은 값으로 계속 갱신만 해주면 되는거다.

말로하려니까 어렵다. 아래에 그림을 참고해라.

관련 문제

https://www.acmicpc.net/problem/11404

https://jinniepark.tistory.com/64

/* 문제설명 */

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

/* 풀이방법 */

https://jinniepark.tistory.com/55

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

//네트워크 연결
public class b1922 {
	static int[] parent;
	static int find(int x) {
		if(x==parent[x])
			return x;
		else {
			parent[x]=find(parent[x]);
			return parent[x];
		}
	}
	static void union(int x,int y) {
		x = find(x);
		y = find(y);
		if(x!=y) {
			parent[y]=x;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine());	//노드의 수
		int M = Integer.parseInt(br.readLine());	//간선의 수
		parent = new int[N+1];
		for(int i=1;i<N+1;i++) {
			parent[i] = i;
		}
		
		ArrayList<Edgee> edges = new ArrayList<Edgee>();
		for(int i=1;i<M+1;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges.add(new Edgee(a,b,c));
		}
		
		Collections.sort(edges);
		int total = 0;
		while(!edges.isEmpty()) {
			Edgee e = edges.remove(0);
			if(find(e.a)==find(e.b)) continue;
			total += e.weight;
			union(e.a,e.b);
		}
		System.out.println(total);
	}
}

class Edgee implements Comparable<Edgee>{
	int a;
	int b;
	int weight;
	
	public Edgee(int a, int b, int weight) {
		super();
		this.a = a;
		this.b = b;
		this.weight = weight;
	}

	@Override
	public int compareTo(Edgee o) {
		return Integer.compare(this.weight, o.weight);
	}
}

Kruskal 알고리즘 

MST(최소 신장 트리)를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

오늘은 크루스칼 알고리즘에 대해 더 자세히 살펴보도록 하겠다.

크루스칼 알고리즘은 일단 모든 간선을 오름차순으로 정렬하고

순서대로 이어나가다가 사이클이 발생하면 해당 간선은 건너뛴다. 참으로 간단하다.

크루스칼은 프림에 비해 희소 그래프인 경우, 그러니까 간선이 적은 경우 적합하고,

프림은 크루스칼에 비해 간선이 많이 존재하는 밀집그래프에 더 적합하다.

프림 알고리즘은 아래에서 더 자세하게 다룬다.

https://jinniepark.tistory.com/46

일단을 개념적으로 구하는 방법을 그려보았다.

이때 사이클을 검사하는 알고리즘은 Union-Find 알고리즘이 쓰인다.

관련문제

https://www.acmicpc.net/problem/1922

https://jinniepark.tistory.com/56?category=952224

/* 문제설명 */

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

/* 풀이방법 */

이문제는 아~주 유명한 Knapsack algorithm을 사용해서 풀어야 한다.

베낭 알고리즘은 두가지 종류가 있는데,

물품을 쪼갤수 있는 Fraction Knapsack problem과 물건을 쪼갤 수 없는 0/1 Knapsack problem으로 나뉜다.

Fraction Knapsack problem는 그리드 알고리즘을 활용해야 하며, 0/1 Knapsack problem는 DP로 풀어야한다.

위의 문제는 물건을 쪼갤 수 없으므로 DP로 풀어야 한다..

자 그럼 최대 이윤을 배열에 저장해 가면서 풀어보자.

일단 최대 이윤을 저장하기 위해 아래와 같은 표를 만들었다.

여기서 아이템들은 백준문제의 예시를 그대로 사용했다.

아이템1은 무게 6, 가치 13 

아이템2는 무게 4, 가치 8

아이템3은 무게 3, 가치 6

아이템4는 무게 5, 가치 12를 지닌다.

이제 값을 저장해보자..

나는 나중에 코드 짤때, 범위인지 아닌지 알아내는거 쓰기 귀찮아서 위에 0번째 줄을 제로패딩 해줬다.

아이템1은 무게 6, 가치 13를 지닌다는 점을 생각하면서 채우자

일단 여기까지는 무난하게 진행된다. 이제 무게가 6kg면 아이템1은 담는게 가능하므로 저칸에 최고 가치인 13을 쓰게 된다.

자 그리고 옆칸도 무게 7에 아이템1만 있을 경우의 최고 가치이므로 당연히 13이 될 것이다.

이런식으로 다음줄도 채워보겠다. 아이템2는 무게 4, 가치 8을 지닌다.

사실 이때부터 비교해 주어야 할칸이 총 세칸이다.

일단 (2,5)에 위치한 초록색 칸이 의미하는 바에 대해 다시 생각해 봐야한다.

무게 제한이 5kg일때, 아이템 1,2만 가지고 가질수있는 최대 가치를 표현해야한다.

그러면 저 값을 위해 비교해야할 값은

첫째, 바로전 (2,4)에 위치한 연두색 칸이다. 해당 칸이 의미하는 바는 4kg제한에서 아이템 1,2만으로 가질수 있는 최대 가치이다. 1kg 늘어났다고해서 달라지는 바가 없을 수도 있지 않은가?

둘째, 바로위 (1,5)에 위치한 연두색 칸이다. 해당 칸이 의미하는 바는 5kg제한에서 아이템 1만으로 가질수 있는 최대 가치이다. 물건 하나 늘어났다고 해서 달라지는 바가 없을 수도 있지 않은가?

셋째는... 현재 아이템 무게를 뺀 가방에서 가질 수 있는 최고 가치와 현재 아이템의 가치를 더한 값이다.

해당 칸에서는 아이템2의 무게는 4이고 이번 문제에서 넣었던 물건은 또 넣을 수 없으므로, 

(1,1)에 위치한 주황색 칸에 있는 값이 최고 가치가 되는 것이다. 

이중 가장 큰값은 8 이므로 (2,5)에는 8을 입력하게 된다. 

사실 위와 같은 방법으로 계속 채워주면 된다.

자 채우고 채워서 여기까지 왔다.

사실 여기도 아까와 같은 방법으로 하면되는데, 다시한번 보겠다.

연두색 칸들이랑, 주황색칸 + 현재가치 중 가장 큰값을 택하면 된다.

지금 아이템3에 위치하고 있으므로 현재가치는 6. 따라서 6+8=14가 된다.

그럼 초록색 칸에는 가장 큰값인 14를 입력하게 된다.

다음줄도 마저 입력해보면..

이런 모양이 되고, 해당 예시에서 원하는 아이템 1,2,3,4를 가지고 7키로 제한의 가장 큰 가치는 (4,7)에 위치한 14가 되는것이다.

조만간 dp에 대해서도 한번 정리해야겠다는걸 많이 느꼈다..

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//평범한 베낭
public class b12865 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] w = new int[N+1];
		int[] v = new int[N+1];
		int[][] memo =new int[N+1][K+1];
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken());
			v[i] = Integer.parseInt(st.nextToken());
		}

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				int pw = w[i];
				int pv = v[i];
				if(pw > j){
					memo[i][j] = memo[i-1][j];
	            }
	  			else{
	  				memo[i][j] = Math.max(memo[i-1][j], pv+memo[i-1][j-pw]);
	            }
			}
		}
		System.out.println(memo[N][K]);	
	}
}

/* 문제설명 */

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE&problemTitle=%ED%95%98%EB%82%98%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

로그인해야 볼 수 있습니다.

/* 풀이방법 */

프림 알고리즘을 사용해서 풀었다.

다만, 문제에 자세히 설명이 안되어져있어서 좀 헤맸는데, 유클리드 거리를 사용해서 두 섬 사이의 거리를 구한다는 점과 우선 터널의 길이를 구하고 맨 마지막에 다 더해서 반올림 한다는 점만 조심하면 괜찮았다.

https://jinniepark.tistory.com/46?category=956229 

5개의 섬이 있는 예시를 하나 들자면 이렇다.

일단 힙에는 터널이 들어갈꺼다. 터널은 (목적지, 거리)형태로 넣어야하는데

어쩌피 다 그래프가 연결되어질꺼라는 가정이 있기 때문에 그냥 아무거나 넣으면 된다. 난 0번을 넣었다.

그럼 아래와 같은 형태가 된다. 아무곳도 아직 방문하지 않았고, Heap에는 초기값만 들어있는 상태이다.

우선순위큐는 거리가 최소가 되어야하기 때문에 거리를 기준으로 오름차순으로 정렬한다.

그러면 일단 우선순위큐에서 값을 하나 꺼낸다. 

그리고 그 섬과 모든 섬과의 거리를 재서 큐에 넣는다. 큐는 당연히 자동으로 거리를 기준으로 오름차순으로 정렬해준다.

그리고 0번섬을 방문했음을 표시하고 가장 짧은 거리를 기록한다.

(코드에서는 기록하지는 않고 바로 total에 더했다)

위와 같은 과정을 반복하면된다.

다시 큐에서 꺼내고, 추가하고, 기록한다.

꺼내고 추가하고 기록

ㄲㄴㄱ ㅊㄱㅎㄱ ㄱㄹ

poll, offer, write

이렇게 모든 곳을 방문했으면 끝이당.

/* 해답코드 */

package samsung;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class b1251 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			int N = Integer.parseInt(br.readLine());
			Island[] island = new Island[N];
			StringTokenizer xs = new StringTokenizer(br.readLine());
			StringTokenizer ys = new StringTokenizer(br.readLine());
			for(int n=0;n<N;n++) {
				int x = Integer.parseInt(xs.nextToken());
				int y = Integer.parseInt(ys.nextToken());
				island[n]=new Island(x,y);
			}
			double E = Double.parseDouble(br.readLine());
			
			PriorityQueue<Tunnel> q = new PriorityQueue<Tunnel>();
			boolean[] visited = new boolean[N];
			q.add(new Tunnel(0,0));
			int cnt=0;
			double total=0;
			while(!q.isEmpty()) {
				Tunnel tunnel = q.poll();
				if(visited[tunnel.dstn])continue;
				visited[tunnel.dstn]=true;
				
				
				total+=(tunnel.length*tunnel.length*E);
				for(int i=0;i<N;i++) {
					if(!visited[i]) {
						q.add(new Tunnel(i,getDistance(island[tunnel.dstn],island[i])));
					}
				} 
				if(++cnt==N)break;
				//System.out.printf("#%d %d %d\n",cnt,island[tunnel.dstn].x,island[tunnel.dstn].y);
			}
			
			System.out.format("#%d %.0f\n",t,total);
		}

	}
	private static double getDistance(Island i1, Island i2) {
		return Math.sqrt(Math.pow(i1.x-i2.x,2)+ Math.pow(i1.y-i2.y,2));
	}

}

class Island{
	public int x;
	public int y;
	public Island(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

class Tunnel implements Comparable<Tunnel>{
	public int dstn;
	public double length;
	public Tunnel(int dstn, double length) {
		super();
		this.dstn = dstn;
		this.length = length;
	}
	@Override
	public int compareTo(Tunnel o) {
		return Double.compare(this.length, o.length);
	}
}

/* 문제설명 */

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

/* 풀이방법 */

문제를 똑바로 안읽어서 고생했다. 한마리 먹을 때마다 몸집이 커지는게 아니라 자신의 몸집 크기만큼 먹었을때 사이즈가 증가한다. 제발 문제좀 제대로 읽자.

최단경로를 구해야하므로 기본적으로 BFS알고리즘을 사용했다.

물고기의 우선순위를 정하는 법이 상당히 까다로웠는데, 처음에는 방향 순회 순서로 우선순위를 정하고자 하였으나,

방향 순회 순서로 절때 구할 수 없다. 따라서 만약에 먹이타겟이 발견되면 그 같은 길이에 있는 곳까지 탐색한 후 직접 일일이 좌표를 비교해줘야 했다..

그점만 유의하면 쉽게 풀 수 있다.

(+) 시간을 줄일 아이디어

아마 우선순위 큐 사용하면 훨씬더 속도면에서 개선될 듯하다.

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

//아기상어
public class b16236 {
	public static int N;
	public static int[][] map;
	public static int[] dx = { -1, 0, 0, 1 };// 상, 좌, 우, 하
	public static int[] dy = { 0, -1, 1, 0 };// 상, 좌, 우, 하

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		Fish shark = null;
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken());
				if (map[n][m] == 9) {
					shark = new Fish(n, m, 2);
					map[n][m] = 0;
				}
			}
		}
		System.out.println(bfs(shark));
	}

	private static int bfs(Fish shark) {
		while (true) {
			Queue<Integer[]> q = new LinkedList<>();
			int[][] visited = new int[N][N];
			List<Fish> fishList = new ArrayList<>();
			q.add(new Integer[] { shark.x, shark.y });
			boolean findFish = false;
			while (!q.isEmpty()) {
				Integer[] point = q.remove();
				int x = point[0];
				int y = point[1];
				// System.out.printf("%d %d\n",x,y);
				if (map[x][y] < shark.size && map[x][y] != 0) {
					Fish f = new Fish(x, y);
					f.dist = visited[x][y];
					fishList.add(f);
					findFish = true;
				}
				if (!findFish) {
					for (int d = 0; d < 4; d++) {
						int nx = x + dx[d];
						int ny = y + dy[d];
						if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] <= shark.size
								&& visited[nx][ny] == 0) {
							visited[nx][ny] = visited[x][y] + 1;
							q.add(new Integer[] { nx, ny });
						}
					}
				}
			}

			if (fishList.size() == 0)
				return shark.time;
			else {
				Collections.sort(fishList);
				Fish f = fishList.remove(0);
				map[f.x][f.y] = 0;
				shark.cnt++;
				if (shark.size == shark.cnt) {
					shark.cnt = 0;
					shark.size++;
				}
				shark.x = f.x;
				shark.y = f.y;
				shark.time += visited[f.x][f.y];
				//System.out.printf("##%d %d %d\n", f.x, f.y, shark.time);
			}

		}
	}
}

class Fish implements Comparable<Fish> {
	public int size;
	public int x;
	public int y;
	public int cnt;
	public int time;
	public int dist;

	public Fish() {
	}

	public Fish(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public Fish(int x, int y, int size) {
		this.cnt = 0;
		this.time = 0;
		this.size = size;
		this.x = x;
		this.y = y;
	}

	@Override
	public int compareTo(Fish o) {
		if (this.dist == o.dist) {
			if (this.x == o.x) {
				return this.y - o.y;
			} else
				return this.x - o.x;
		} else
			return this.dist - o.dist;
	}
}

/* 문제설명 */

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

/* 풀이방법 */

PRIM알고리즘을 사용해서 풀이했다.

https://jinniepark.tistory.com/46

/* 해답코드 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//최소 스피닝 트리
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		ArrayList<Edge>[] adjList = new ArrayList[V+1];
		for(int i=1;i<=V;i++) {
			adjList[i] = new ArrayList<Edge>();
		}
		for(int i=0;i<E;i++) {
			st =new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adjList[s].add(new Edge(e,w));
			adjList[e].add(new Edge(s,w));
		}
		
		int[] min_edge = new int[V+1];
		Arrays.fill(min_edge, Integer.MAX_VALUE);
		boolean[] visited = new boolean[V+1];
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		q.add(new Edge(1,0));
		
		int cnt=0;
		while(!q.isEmpty()) {
			Edge edge = q.poll();
			if(visited[edge.n])continue;
			
			visited[edge.n]=true;
			min_edge[edge.n] = edge.dist;
			for(Edge next : adjList[edge.n]) {
					if(!visited[next.n]) {
						q.add(next);
				}
			}
			if(++cnt==V)break;
		}
		int sum=0;
		for(int i=1;i<=V;i++) {
			sum+=min_edge[i];
		}
		System.out.println(sum);
	}
}


class Edge implements Comparable<Edge>{
	int n;
	int dist;
	public Edge(int n, int dist) {
		super();
		this.n = n;
		this.dist = dist;
	}

	@Override
	public int compareTo(Edge o) {
		return Integer.compare(this.dist, o.dist);
	}
}