結果
| 問題 |
No.1320 Two Type Min Cost Cycle
|
| ユーザー |
 manta1130
|
| 提出日時 | 2020-12-18 20:58:52 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,688 bytes |
| コンパイル時間 | 12,554 ms |
| コンパイル使用メモリ | 378,568 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-21 09:22:32 |
| 合計ジャッジ時間 | 15,847 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 50 WA * 7 |
コンパイルメッセージ
warning: unused attribute `macro_export`
--> src/main.rs:122:5
|
122 | #[macro_export]
| ^^^^^^^^^^^^^^^
|
note: the built-in attribute `macro_export` will be ignored, since it's applied to the macro invocation `thread_local`
--> src/main.rs:123:5
|
123 | thread_local! {
| ^^^^^^^^^^^^
= note: `#[warn(unused_attributes)]` on by default
warning: unused variable: `i`
--> src/main.rs:7:9
|
7 | for i in 0..m {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
ソースコード
fn main() {
inputv! {
t:usize,
n:usize,m:usize,
}
let mut graph = vec![vec![]; n * 2];
for i in 0..m {
inputv! {
u:usize,v:usize,w:isize
}
graph[2 * (u - 1) + 1].push((2 * (v - 1), w));
if t == 0 {
graph[2 * (v - 1)].push((2 * (u - 1) + 1, w));
}
}
for i in 0..n {
graph[2 * i].push((2 * i + 1, 0));
}
let mut ans = isize::max_value();
for i in 0..n {
let r = dijkstra(&graph, 2 * i + 1);
ans = std::cmp::min(ans, r[2 * i]);
}
println!("{}", if ans == isize::max_value() { -1 } else { ans });
}
//https://github.com/manta1130/competitive-template-rs
use graph::*;
use input::*;
pub mod graph {
use std::cmp;
use std::collections::BinaryHeap;
#[allow(clippy::ptr_arg)]
pub fn bellman_ford(graph: &Vec<Vec<(usize, isize)>>, dist: &mut [Option<isize>]) -> Vec<bool> {
let mut neg_flag = vec![false; dist.len()];
for _ in 0..graph.len() {
for (from, v) in graph.iter().enumerate() {
for e in v.iter() {
let cost = e.1;
let to = e.0;
if let Some(x) = dist[from] {
if dist[to].is_none() {
dist[to] = Some(x + cost);
} else if let Some(y) = dist[to] {
if y > x + cost {
dist[to] = Some(x + cost);
}
}
}
}
}
}
for _ in 0..graph.len() {
for (from, v) in graph.iter().enumerate() {
for e in v.iter() {
let cost = e.1;
let to = e.0;
if let Some(x) = dist[from] {
if dist[to].is_none() {
dist[to] = Some(x + cost);
neg_flag[to] = true;
} else if let Some(y) = dist[to] {
if y > x + cost {
dist[to] = Some(x + cost);
neg_flag[to] = true;
}
}
}
if neg_flag[from] {
neg_flag[to] = true;
}
}
}
}
neg_flag
}
#[allow(clippy::ptr_arg)]
pub fn dijkstra(graph: &Vec<Vec<(usize, isize)>>, start: usize) -> Vec<isize> {
let mut heap = BinaryHeap::new();
let mut dist = vec![isize::max_value(); graph.len()];
dist[start] = 0;
heap.push((0_isize, start));
while !heap.is_empty() {
let e = heap.pop().unwrap();
if e.0.wrapping_neg() > dist[e.1] {
continue;
}
for next_e in graph[e.1].iter() {
if dist[next_e.0] > next_e.1 + dist[e.1] {
dist[next_e.0] = next_e.1 + dist[e.1];
heap.push(((dist[e.1] + next_e.1).wrapping_neg(), next_e.0));
}
}
}
dist
}
pub fn warshall_floyd(graph: &mut [&mut [isize]]) {
for k in 0..graph.len() {
for i in 0..graph.len() {
for j in 0..graph.len() {
graph[i][j] = cmp::min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
}
pub mod input {
use std::cell::RefCell;
use std::io;
pub const SPLIT_DELIMITER: char = ' ';
pub use std::io::prelude::*;
#[macro_export]
thread_local! {
pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
}
#[macro_export]
macro_rules! input_internal {
($x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let $x: $t = buf_split_result.parse().unwrap();
};
(mut $x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let mut $x: $t = buf_split_result.parse().unwrap();
};
}
#[macro_export]
macro_rules! inputv {
($i:ident : $t:ty) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty) => {
input_internal!{mut $i : $t}
};
($i:ident : $t:ty $(,)*) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty $(,)*) => {
input_internal!{mut $i : $t}
};
(mut $i:ident : $t:ty,$($q:tt)*) => {
input_internal!{mut $i : $t}
inputv!{$($q)*}
};
($i:ident : $t:ty,$($q:tt)*) => {
input_internal!{$i : $t}
inputv!{$($q)*}
};
}
pub fn input_all() {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let mut temp_str = String::new();
std::io::stdin().read_to_string(&mut temp_str).unwrap();
let mut split_result_iter = temp_str
.split_whitespace()
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
}
pub fn input_line_str() -> String {
let mut s = String::new();
io::stdin().read_line(&mut s).unwrap();
s.trim().to_string()
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector<T>() -> Vec<T>
where
T: std::str::FromStr,
{
let mut v: Vec<T> = Vec::new();
let s = input_line_str();
let split_result = s.split(SPLIT_DELIMITER);
for z in split_result {
let buf = match z.parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector_row<T>(n: usize) -> Vec<T>
where
T: std::str::FromStr,
{
let mut v = Vec::with_capacity(n);
for _ in 0..n {
let buf = match input_line_str().parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
pub trait ToCharVec {
fn to_charvec(&self) -> Vec<char>;
}
impl ToCharVec for String {
fn to_charvec(&self) -> Vec<char> {
self.to_string().chars().collect::<Vec<_>>()
}
}
}