結果

問題 No.5007 Steiner Space Travel
ユーザー ainem-mainem-m
提出日時 2023-04-27 16:08:21
言語 Rust
(1.77.0)
結果
AC  
実行時間 675 ms / 1,000 ms
コード長 6,756 bytes
コンパイル時間 1,625 ms
コンパイル使用メモリ 157,256 KB
実行使用メモリ 4,372 KB
スコア 7,620,588
最終ジャッジ日時 2023-04-27 16:08:40
合計ジャッジ時間 19,070 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 441 ms
4,368 KB
testcase_01 AC 545 ms
4,372 KB
testcase_02 AC 563 ms
4,368 KB
testcase_03 AC 561 ms
4,372 KB
testcase_04 AC 498 ms
4,368 KB
testcase_05 AC 575 ms
4,368 KB
testcase_06 AC 532 ms
4,372 KB
testcase_07 AC 545 ms
4,368 KB
testcase_08 AC 524 ms
4,372 KB
testcase_09 AC 428 ms
4,372 KB
testcase_10 AC 512 ms
4,368 KB
testcase_11 AC 513 ms
4,372 KB
testcase_12 AC 590 ms
4,368 KB
testcase_13 AC 373 ms
4,368 KB
testcase_14 AC 385 ms
4,368 KB
testcase_15 AC 563 ms
4,368 KB
testcase_16 AC 439 ms
4,368 KB
testcase_17 AC 466 ms
4,368 KB
testcase_18 AC 528 ms
4,368 KB
testcase_19 AC 574 ms
4,372 KB
testcase_20 AC 399 ms
4,368 KB
testcase_21 AC 675 ms
4,372 KB
testcase_22 AC 373 ms
4,368 KB
testcase_23 AC 482 ms
4,372 KB
testcase_24 AC 365 ms
4,368 KB
testcase_25 AC 442 ms
4,372 KB
testcase_26 AC 370 ms
4,368 KB
testcase_27 AC 674 ms
4,372 KB
testcase_28 AC 492 ms
4,368 KB
testcase_29 AC 467 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::BinaryHeap;

const INF: i32 = 1000000000;

/// 作問者terry_u16さんの提出から頂いた
/// 入力受け取り用のマクロ
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

/// Rustでは入力から受け取った変数を
/// グローバルに定義することが難しいので
/// 構造体として持つと便利
#[allow(dead_code)]
#[derive(Debug, Clone)]
struct Input {
    n: usize,
    m: usize,
    points: Vec<Point>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
    fn new(x: i32, y: i32) -> Self {
        Self { x, y }
    }
    fn dist_sq(&self, other: &Self) -> i32 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx * dx + dy * dy) as i32
    }
}

fn main() {
    let input = read_input();
    let mut points = input.points.clone();
    //     宇宙ステーションの座標は適当に決め打ち
    //
    //   x  x  x
    //   x     x
    //   x  x  x
    //
    // みたいにする
    points.push(Point::new(300, 300));
    points.push(Point::new(300, 500));
    points.push(Point::new(300, 700));
    points.push(Point::new(500, 300));
    points.push(Point::new(500, 700));
    points.push(Point::new(700, 300));
    points.push(Point::new(700, 500));
    points.push(Point::new(700, 700));

    // ワーシャルフロイド法で全頂点対の最短経路を求める
    let distances = warshall_floyd(&input, &points);

    // 経路の作成（貪欲法）

    // 惑星1から出発し、一番近い惑星を貪欲に選び続ける（Nearest Neighbour法）
    let mut v = 0;
    let mut visited = vec![false; input.n];
    visited[0] = true;
    let mut route = vec![0];

    // 惑星1以外のN-1個の惑星を訪問していく
    for _ in 0..input.n - 1 {
        let mut nearest_dist = INF;
        let mut nearest_v = !0;

        // 一番近い惑星を探す
        for next in 0..input.n {
            if visited[next] {
                continue;
            }

            if distances[v][next] < nearest_dist {
                nearest_dist = distances[v][next];
                nearest_v = next;
            }
        }

        // パスを復元
        let mut path = dijkstra(&input, &points, v, nearest_v);
        route.append(&mut path);

        // 次の頂点に移動
        v = nearest_v;
        visited[v] = true;
    }

    // 最後に惑星1に戻る必要がある
    let mut path = dijkstra(&input, &points, v, 0);
    route.append(&mut path);

    // 解の出力

    // 宇宙ステーションの座標を出力
    for Point { x, y } in points.iter().skip(input.n) {
        println!("{x} {y}");
    }

    // 経路の長さを出力
    println!("{}", route.len());

    // 経路を出力
    for v in route {
        if v < input.n {
            println!("1 {}", v + 1);
        } else {
            println!("2 {}", v - input.n + 1);
        }
    }
}

/// 入力読み込み
fn read_input() -> Input {
    let (n, m) = get!(usize, usize);

    let mut points = vec![];

    for _ in 0..n {
        let (x, y) = get!(i32, i32);
        points.push(Point::new(x, y));
    }

    Input { n, m, points }
}

/// エネルギー計算
fn calc_energy(input: &Input, points: &Vec<Point>, i: usize, j: usize) -> i32 {
    let mut energy = points[i].dist_sq(&points[j]);
    if i < input.n {
        energy *= 5;
    }
    if j < input.n {
        energy *= 5;
    }
    energy
}

/// ワーシャルフロイド法によって、O(v^3)で全頂点対の最短経路長を求める
fn warshall_floyd(input: &Input, points: &Vec<Point>) -> Vec<Vec<i32>> {
    let mut distances = vec![vec![0; points.len()]; points.len()];
    // 全点間エネルギーを計算
    for i in 0..points.len() {
        for j in 0..points.len() {
            distances[i][j] = calc_energy(input, points, i, j);
        }
    }
    // ワーシャルフロイド
    for k in 0..points.len() {
        for i in 0..points.len() {
            for j in 0..points.len() {
                let d = distances[i][k] + distances[k][j];
                distances[i][j] = distances[i][j].min(d);
            }
        }
    }
    distances
}

/// ダイクストラ法を用いて、経由点iから経由点jへの最短経路を復元する関数
fn dijkstra(input: &Input, points: &Vec<Point>, i: usize, j: usize) -> Vec<usize> {
    let mut dijkstra_dist = vec![INF; points.len()];

    // 1つ前にいた頂点を保存する配列(経路復元用)
    let mut prev_points = vec![!0; points.len()];

    // (経路、頂点)のペアをpush
    let mut queue = BinaryHeap::from(vec![(0, i)]);
    dijkstra_dist[i] = 0;

    while let Some((d, v)) = queue.pop() {
        if d > dijkstra_dist[v] {
            continue;
        }

        for next in 0..points.len() {
            let next_d = d + calc_energy(input, points, v, next);
            if next_d < dijkstra_dist[next] {
                // 1つ前の頂点を保存しておく
                prev_points[next] = v;
                dijkstra_dist[next] = next_d;
                queue.push((next_d, next));
            }
        }
    }

    // ここから経路復元
    // ゴールから1つずつ頂点をたどっていく
    // パンくずみたいな感じ
    let mut v = j;
    let mut path = vec![];

    // スタートに戻るまでループ
    while v != i {
        path.push(v);
        v = prev_points[v];
    }

    // pathには経路が逆順で入っているのでひっくり返す
    path.reverse();

    path
}
0