백준 1277번
https://www.acmicpc.net/problem/1277
다익스트라이다.
기존의 가중치 값이 그저 좌표상의 거리가 될 뿐이다.
M
거리를 넘지않는다는 조건에서 모든 노드가 연결되어있다고 생각하면 됨
import java.io.*;
import java.util.*;
public class Main {
// input
private static BufferedReader br;
// variables
private static final int INF = Integer.MAX_VALUE;
private static int N;
private static List<List<Node>> adjList;
private static class Node implements Comparable<Node> {
int num;
double dist;
private Node(int num, double dist) {
this.num = num;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
return Double.compare(dist, o.dist);
}
} // End of Node class
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
double ans = dijkstra() * 1000;
sb.append((int) ans);
return sb.toString();
} // End of solve()
private static double dijkstra() {
PriorityQueue<Node> pQue = new PriorityQueue<>();
boolean[] isVisited = new boolean[N + 1];
double[] dist = new double[N + 1];
Arrays.fill(dist, INF);
dist[1] = 0;
pQue.offer(new Node(1, 0.0));
while (!pQue.isEmpty()) {
Node current = pQue.poll();
if (dist[current.num] < current.dist) continue;
if (isVisited[current.num]) continue;
isVisited[current.num] = true;
for (Node next : adjList.get(current.num)) {
if (dist[next.num] > dist[current.num] + next.dist) {
dist[next.num] = dist[current.num] + next.dist;
pQue.offer(new Node(next.num, dist[next.num]));
}
}
}
return dist[N];
} // End of dijkstra()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
double m = Double.parseDouble(br.readLine());
int[][] powers = new int[N + 1][2];
adjList = new ArrayList<>();
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
powers[i][0] = Integer.parseInt(st.nextToken());
powers[i][1] = Integer.parseInt(st.nextToken());
adjList.add(new ArrayList<>());
}
adjList.add(new ArrayList<>());
for (int i = 1; i <= N; i++) {
int currentX = powers[i][0];
int currentY = powers[i][1];
for (int j = i + 1; j <= N; j++) {
double diff = Math.sqrt(Math.pow(currentX - powers[j][0], 2) + Math.pow(currentY - powers[j][1], 2));
if (diff > m) continue;
adjList.get(i).add(new Node(j, diff));
adjList.get(j).add(new Node(i, diff));
}
}
for (int i = 0; i < w; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adjList.get(a).add(new Node(b, 0));
adjList.get(b).add(new Node(a, 0));
}
} // End of input()
} // End of Main class