結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-11 10:55:08 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 3,328 bytes |
コンパイル時間 | 4,842 ms |
コンパイル使用メモリ | 79,224 KB |
実行使用メモリ | 41,848 KB |
最終ジャッジ日時 | 2024-11-11 10:55:18 |
合計ジャッジ時間 | 8,106 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import java.io.*;import java.util.*;import java.util.function.*;import java.util.stream.*;public class Main {static double[] dp;public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();int k = sc.nextInt();Point[] points = new Point[n];for (int i = 0; i < n; i++) {points[i] = new Point(sc.nextInt(), sc.nextInt());}double[][] matrix = new double[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = points[i].getDistance(points[j]);}}dp = new double[1 << n];Arrays.fill(dp, Double.MAX_VALUE);dp[0] = 0;double[][] routes = new double[n][1 << n];for (int i = 1; i < (1 << n); i++) {int count = Integer.bitCount(i);if (count > k) {continue;}for (int j = 0; j < n; j++) {if ((i & (1 << j)) == 0) {continue;}if (count == 1) {routes[j][i] = points[j].getFromBase();} else {routes[j][i] = Double.MAX_VALUE;for (int a = 0; a < n; a++) {if (a == j || (i & (1 << a)) == 0) {continue;}routes[j][i] = Math.min(routes[j][i], routes[a][i ^ (1 << j)] + matrix[a][j]);}}dp[i] = Math.min(dp[i], routes[j][i] + points[j].getFromBase());}}System.out.println(new java.math.BigDecimal(dfw((1 << n) - 1)).toPlainString());}static double dfw(int mask) {if (dp[mask] == Double.MAX_VALUE) {for (int x = ((mask - 1) & mask); x > 0; x = ((x - 1) & mask)) {dp[mask] = Math.min(dp[mask], dfw(x) + dfw(mask ^ x));}}return dp[mask];}static class Point {double x;double y;public Point(double x, double y) {this.x = x;this.y = y;}public double getDistance(Point p) {return Math.sqrt(Math.pow(x - p.x, 2) + Math.pow(y - p.y, 2));}public double getFromBase() {return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));}}}class Scanner {BufferedReader br;StringTokenizer st = new StringTokenizer("");public Scanner() {try {br = new BufferedReader(new InputStreamReader(System.in));} catch (Exception e) {}}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public String next() {try {while (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}} catch (Exception e) {e.printStackTrace();} finally {return st.nextToken();}}}