結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 matsu7874
|
| 提出日時 | 2022-07-30 17:35:13 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 9 ms / 1,000 ms |
| コード長 | 7,386 bytes |
| コンパイル時間 | 1,131 ms |
| 実行使用メモリ | 5,452 KB |
| スコア | 6,026,701 |
| 最終ジャッジ日時 | 2022-07-30 17:35:16 |
| 合計ジャッジ時間 | 3,010 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
warning: unused import: `std::cmp::Reverse`
--> Main.rs:1:5
|
1 | use std::cmp::Reverse;
| ^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `std::collections::BinaryHeap`
--> Main.rs:2:5
|
2 | use std::collections::BinaryHeap;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: value assigned to `t` is never read
--> Main.rs:10:17
|
10 | let mut t = 0;
| ^
|
= note: `#[warn(unused_assignments)]` on by default
= help: maybe it is overwritten before being read?
warning: unused variable: `cluster_ids`
--> Main.rs:134:5
|
134 | cluster_ids: &[usize],
| ^^^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_cluster_ids`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `n`
--> Main.rs:211:10
|
211 | let (n, m, planets) = read_input();
| ^ help: if this is intentional, prefix it with an underscore: `_n`
warning: 5 warnings emitted
ソースコード
use std::cmp::Reverse;use std::collections::BinaryHeap;static mut XORSHIFT1: u128 = 123456789;static mut XORSHIFT2: u128 = 362436069;static mut XORSHIFT3: u128 = 521288629;static mut XORSHIFT4: u128 = 88675123;fn xorshift() -> u128 {unsafe {let mut t = 0;t = XORSHIFT1 ^ (XORSHIFT1 << 11u128);XORSHIFT1 = XORSHIFT2;XORSHIFT2 = XORSHIFT3;XORSHIFT3 = XORSHIFT4;XORSHIFT4 = (XORSHIFT4 ^ (XORSHIFT4 >> 19u128)) ^ (t ^ (t >> 8u128));t}}fn read_input() -> (usize, usize, Vec<(i32, i32)>) {let (n, m) = {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let s = s.trim_end().to_owned();let mut ws = s.split_whitespace();let n: usize = ws.next().unwrap().parse().unwrap();let m: usize = ws.next().unwrap().parse().unwrap();(n, m)};let mut xy = vec![];for _ in 0..n {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let s = s.trim_end().to_owned();let mut ws = s.split_whitespace();let a: i32 = ws.next().unwrap().parse().unwrap();let b: i32 = ws.next().unwrap().parse().unwrap();xy.push((a, b));}(n, m, xy)}const MAX_X: i32 = 1000;type Point = (i32, i32);// fn dist(p: &Point, q: &Point) -> i32 {// (((p.0 - q.0) * (p.0 - q.0) + (p.1 - q.1) * (p.1 - q.1)) as f64).sqrt() as i32// }fn dist_powered(p: &Point, q: &Point) -> i32 {(p.0 - q.0) * (p.0 - q.0) + (p.1 - q.1) * (p.1 - q.1)}fn kmeans(points: &[Point], k: usize, max_iter: usize) -> (Vec<Point>, Vec<usize>) {let n = points.len();let mut centors = Vec::with_capacity(k);for _ in 0..k {centors.push(((xorshift() as i32).abs() % (MAX_X + 1),(xorshift() as i32).abs() % (MAX_X + 1),));}let mut cluster_ids = vec![0; n];let mut cluster_sizes = vec![0; k];cluster_sizes[0] = n as i32;let mut updated = false;for loop_count in 0..max_iter {// 各点から最も近い代表点を探すfor i in 0..n {let mut nearest_centor_id = 0;let mut nearest_centor_distance = dist_powered(&points[i], ¢ors[0]);for j in 1..k {let distance = dist_powered(&points[i], ¢ors[j]);if distance < nearest_centor_distance {nearest_centor_distance = distance;nearest_centor_id = j;}}if nearest_centor_id != cluster_ids[i] {cluster_sizes[cluster_ids[i]] -= 1;cluster_ids[i] = nearest_centor_id;cluster_sizes[nearest_centor_id] += 1;updated = true;}}// 代表点の座標をクラスタの中心に移動するlet mut dxs = vec![0; k];let mut dys = vec![0; k];for i in 0..n {let cid = cluster_ids[i];dxs[cid] += points[i].0 - centors[cid].0;dys[cid] += points[i].1 - centors[cid].1;}for i in 0..k {if cluster_sizes[i] == 0 {continue;}centors[i].0 += dxs[i] / cluster_sizes[i];centors[i].1 += dys[i] / cluster_sizes[i];}if !updated {eprintln!("kmeans loop breaked at loop {}", loop_count);break;}}(centors, cluster_ids)}// fn tsp_dp(points:&[Point])->Vec<usize>{// let n = points.len();// let mut dp = vec![]// }const ALPHA: i32 = 5;fn get_cost_coefficient(t1: usize, t2: usize) -> i32 {if t1 == PLANET {if t2 == PLANET {ALPHA * ALPHA} else {ALPHA}} else {if t2 == PLANET {ALPHA} else {1}}}const PLANET: usize = 1;const STATION: usize = 2;fn search_path(stations: &[Point],planets: &[Point],cluster_ids: &[usize],) -> Vec<(usize, usize)> {let n = planets.len();let m = stations.len();// 全点対の最短経路を求めるlet mut next = vec![vec![0; n + m]; n + m];for i in 0..n + m {for j in 0..n + m {next[i][j] = j;}}let mut dist = vec![vec![i32::MAX / 4; n + m]; n + m];for i in 0..n + m {let p = if i < n { planets[i] } else { stations[i - n] };let tp = if i < n { PLANET } else { STATION };for j in 0..n + m {let q = if j < n { planets[j] } else { stations[j - n] };let tq = if i < n { PLANET } else { STATION };dist[i][j] = get_cost_coefficient(tp, tq) * dist_powered(&p, &q);}}for k in 0..n + m {for i in 0..n + m {for j in 0..n + m {if dist[i][k] + dist[k][j] < dist[i][j] {dist[i][j] = dist[i][k] + dist[k][j];next[i][j] = next[i][k];}}}}// 経路を作成するlet mut path = vec![(PLANET, 0)];let mut visited = vec![false; planets.len()];visited[0] = true;let mut count_visited_planets = 1;let mut cur_id = 0;while count_visited_planets < planets.len() {// まだ到達していない惑星のなかで距離が最小のものに移動するlet mut nearest_distance = i32::MAX;let mut nearest = (PLANET, 0);for i in 0..planets.len() {if visited[i] {continue;}// let distance =// get_cost_coefficient(cur_type, PLANET) * dist_powered(&cur_point, &planets[i]);if dist[cur_id][i] < nearest_distance {nearest_distance = dist[cur_id][i];nearest = (PLANET, i);}}// 経路に追加するif nearest.0 == PLANET {count_visited_planets += 1;visited[nearest.1] = true;// 経路復元let mut cur = cur_id;while cur != nearest.1 {cur = next[cur][nearest.1];path.push((if cur < n { PLANET } else { STATION }, cur % n));}}path.push(nearest);cur_id = nearest.1;}path.push((PLANET, 0));path}fn main() {let (n, m, planets) = read_input();let (stations, cluster_ids) = kmeans(&planets, m, 1000);eprintln!("stations: {:?}", stations);let path = search_path(&stations, &planets, &cluster_ids);assert!(path.len() <= 100000);for (x, y) in stations.iter() {println!("{} {}", x, y);}println!("{}", path.len());for (t, i) in path.iter() {println!("{} {}", t, i + 1);}}#[cfg(test)]mod tests {use super::*;#[test]fn test_kmeans() {let points = vec![(10, 10), (1000, 1000), (10, 5), (10, 6)];let (centors, cluster_id) = kmeans(&points, 2, 100);eprintln!("centors:{:?}", centors);eprintln!("cluster_id:{:?}", cluster_id);assert_eq!(cluster_id[0], cluster_id[2]);assert_eq!(cluster_id[0], cluster_id[3]);assert_eq!(centors[cluster_id[0]], (10, 7));assert_eq!(centors[cluster_id[1]], (1000, 1000));}}